Problem Statement

Balanced Prefixes After One Swap You are given a string s consisting only of the characters L and R , containing an equal number of each. The string is said to be balanced at position i if the prefix s[0...i] contains an equal number of L s and R s. Positions are zero-indexed, and the prefix s[0...i] includes the character at index i . You are allowed to perform at most one swap of two adjacent characters of s . That is, you may pick an index j and exchange s[j] with s[j+1] , or you may leave the string untouched. Find the maximum number of balanced prefixes that can be obtained after performing at most one adjacent swap. Worked example Take s = "LLRR" . Without any swap, the prefixes are L , LL , LLR and LLRR . Only LLRR has as many L s as R s, so the string is balanced at exactly one position. Swapping the adjacent characters at indices 1 and 2 turns s into "LRLR" . Its prefixes are L , LR , LRL and LRLR , and two of them are balanced. No adjacent swap does better, so the answer for