FastPrepMaximum Weight of a Binary String
Problems/Maximum Weight of a Binary String

Maximum Weight of a Binary String

Nutanix logoNutanix● MediumINTERNOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A fall-2018 report from a Nutanix intern online assessment spells out, in English, a scoring rule for a string of 0s and 1s. It asks for the best score when characters may be flipped. It points to a similar outside write-up and includes two small samples.

The report does not say how the string is divided into pairs and single characters, and gives no limits. Here, as our reading of its rule, the string is cut into pieces of one or two characters so that each character counts exactly once. Flips are made before the cut. The input is a string of 1 to 10^5 characters. The examples are ours.

Our version is about 85% the same as the reported question.

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 (01 or 10), 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) → int

Examples

Example 1

s = "0010"return = 7

Without 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 = 8

A 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 = 1

The only piece is the single character, worth 1. Flipping it would only cost a point.

Constraints

  • 1 <= s.length <= 10^5
  • s consists 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

Interview reports that mention this question

  • Nutanix SWE Intern OA Questions: 16 Experiences (Part 2 of 3)

Nutanix interview experiences

  • Nutanix SWE Intern Phone Screens: 20 Experiences (Part 3 of 3)
  • Nutanix U.S. SWE Intern Interviews: 54 Experiences (Part 1 of 3)
  • Nutanix SWE OA and Interviews, Level Not Reported: 9 Experiences
  • Nutanix Intern Debugging Round and Interviews: 25 Experiences
All Nutanix interview questionsSee Nutanix hiring insights
Saved
class Solution {
    public int maxStringWeight(String s) {
        // Write your code here.
    }
}
Checking account…