Trim Matching Ends

Medium

You are given a string text of the letters a, b and c. You may repeat the following move any number of times, including zero: - pick a non-empty beginning of the string made of one repeated letter; - pick a non-empty ending of the string made of one repeated letter; - the two pieces must not overlap, and they must use the same letter; - delete both pieces. Return the smallest length the string can be cut down to.

Example 1

text="bacab" → 1

Trim "b" from both ends, then "a", leaving "c". A single letter cannot serve as both the front and the back piece, so the answer is 1.

Example 2

text="abbba" → 0

Trim "a" and "a" to get "bbb", then take "b" from the front and "bb" from the back, and the string is empty.

Example 3

text="ccbacc" → 2

Trim "cc" and "cc" to get "ba". Its ends differ, so nothing more can be cut.

Constraints

1 ≤ len(text) ≤ 10⁶
text consists only of the letters a, b and c

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Two Pointers String

Similar problems

Longest Mirror Fragment Medium Words in Reverse Order Medium Exactly One Edit Apart Medium Which Release Is Newer Medium Reverse the Word Order in Place Medium

Input

text="bacab"

Expected

Run checks the first 3 tests in your browser. Submit checks all 139 tests on the server, hidden ones included.