Number of Good Ways to Split a String
01 · Problem
Given a string s, you may cut it once into a non-empty left part p and a non-empty right part q so that p + q == s. A cut is good if p and q contain the same number of distinct letters.
Return the number of good cuts. A string of length 1 has no possible cut, so the answer for it is 0.
02 · Examples
s = "abab"
1
Splits are a|bab (1 vs 2 distinct), ab|ab (2 vs 2) and aba|b (2 vs 1). Only ab|ab is good.
s = "aaaa"
3
Every split leaves just the letter 'a' on each side, so all 3 splits are good.
s = "abcde"
0
All letters are different, so the left side has i distinct letters and the right side has 5 - i. They are never equal for an odd length.
03 · Constraints
- 011 <= s.length <= 105
- 02s consists of only lowercase English letters
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.