Maximum Weight of a Binary String
Updated
Problem statement
You are given a string s made of the characters '0' and '1'.
First, you may flip any characters you like. A flip turns a 0 into a 1 or a 1 into a 0, and every flipped character costs 1 point.
Then you cut the string into pieces, keeping the characters in order. Every character goes into exactly one piece, and each piece is one of these:
- a single character, worth 1 point, or
- two neighboring characters that are different from each other (
01or10), worth 4 points.
The weight is the total points of all pieces minus the number of flipped characters. Return the largest weight you can get.
Function
maxStringWeight(s: String) → intExamples
Example 1
s = "0010"return = 7Without flips, the best cut is 0 | 01 | 0: 1 + 4 + 1 = 6. Flipping the first character gives 1010, which cuts into 10 | 10: 4 + 4 = 8 points, minus 1 flip, so 7. Two pairs without a flip would need the pieces 00 and 10 to both be pairs, and 00 is not, so 8 is not possible. The answer is 7.
Example 2
s = "10111"return = 8A string of length 5 can hold at most two pairs and one single, worth 9. The three ways to cut it into two pairs and a single are 10 | 11 | 1, 10 | 1 | 11 and 1 | 01 | 11, and each has the piece 11, so 9 is not possible without a flip. Flipping the last character gives 10110, cut as 10 | 1 | 10: 4 + 1 + 4 - 1 = 8. The answer is 8.
Example 3
s = "1"return = 1The only piece is the single character, worth 1. Flipping it would only cost a point.
Constraints
1 <= s.length <= 10^5sconsists only of the characters'0'and'1'.
More Nutanix Online Assessment questions
- Good SubsequencesOA · Seen Jul 2026
- Min Cost to Connect All PointsOA · Seen Jun 2026
- Digit Changes for a Multiple of 9OA · Seen Aug 2025
- Gas Station Loop StartOA · Seen Aug 2025
- Number of Players (for MTS2)OA · Seen Oct 2024
- Work Schedules (for MTS2)OA · Seen Oct 2024
- Minimum Operations to Convert ArrayOA · Seen Apr 2024
- No Adjacent CharactersOA · Seen Apr 2024
- Build a BST From a ListOA · Seen Nov 2022
- Delete Even-Valued Nodes From a Linked ListOA · Seen Nov 2022
Similar questions at other companies
- Maximum Equal-Bit Pairs in a SubsequenceAmazon · OA
- 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