Convert to Good String
Updated
Problem statement
Given a binary string s (a string of the characters '0' and '1'), a good string is one that does not contain a subsequence with the pattern "010" or "101". A subsequence is formed by deleting zero or more characters without changing the order of the remaining ones. In one operation you can flip a character, converting 0 to 1 or 1 to 0. Return the minimum number of operations required to convert the given string to a good string.
Function
convertToGoodString(s: String) → int Complete the function convertToGoodString in the editor.
convertToGoodString has the following parameter:
String s: the binary string
Returns int: the minimum number of operations needed to make s a good string
Examples
Example 1
s = "111101110100"return = 2Flip the 0 at position 5 and the 0 at position 9 (positions count from 1) to 1. The string becomes "111111111100", which has no subsequence "010" or "101". That takes 2 operations, and one operation is not enough.
Constraints
1 <= |s| <= 10^5sconsists only of the characters'0'and'1'
More Amazon interview questions
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Maximal SquareONSITE INTERVIEW · Seen Nov 2026
- Serialize and Deserialize a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Diagonal Traversal of a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Spread Through a GridPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Consistent-Hash Packet RouterPHONE SCREEN · Seen Nov 2026
- Count Connected ComponentsPHONE SCREEN · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
Similar questions at other companies
- Longest Subsequence That Is a SubstringBooking.com · OA
- Count Digit Replacements with No Equal Adjacent DigitsMicrosoft · OAMicrosoft interview questions
- Palindrome CounterGoldman Sachs · OAGoldman Sachs interview questions
- Longest String ChainVisa · OAVisa interview questions
- Minimum-Cost Digit String DecodingSquadStack.ai · OA
- Maximum Redundancy After One Segment FlipBloomberg LP · OABloomberg LP interview questions
- Substrings Without a Target SubsequencePhonePe · OAPhonePe interview questions
- Minimum Edit-Distance String for Each QueryTarget · OA
- Longest Subsequence That Is a SubstringWells Fargo · OAWells Fargo interview questions
- Non-Alternating Binary PartitionsThe D.E. Shaw Group · OAThe D.E. Shaw Group interview questions