Split a String So Each Letter Stays in One Part
You are given a string s of lowercase English letters.
Cut s into parts. Each part is a non-empty block of neighbouring characters, and the parts, read in order, give s again.
There is one rule: every letter must appear in only one part. All copies of the same letter must be inside the same part.
Return the largest number of parts you can make.
Hint: first find the last position of every letter. Then walk through the string. The current part cannot end before the last position of any letter you have seen in it.
Examples
Example 1
- Input:
- "xyxzwqwkk"
- Output:
- 4
The parts are "xyx", "z", "wqw" and "kk". Each letter is inside one part only. No part can be cut again: "xyx" must stay together because of its two x letters, and "wqw" because of its two w letters.
Example 2
- Input:
- "mnonm"
- Output:
- 1
The first and last letters are both m, so the whole string must be one part.
Example 3
- Input:
- "abcd"
- Output:
- 4
Every letter appears once, so each letter can be its own part.
Constraints
1 <= s.length <= 60shas only lowercase English lettersatoz.
Run checks your code against the 3 examples. Submit checks it against all 203 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.