Palindrome-Ready Substrings
HardArrays & Hashing
Problem
A word-game generator only accepts letter tiles from a to j. A run of tiles is palindrome-ready if its tiles can be rearranged into a palindrome, i.e. at most one letter appears an odd number of times.
Given the string s, return the number of non-empty substrings (counted by position) that are palindrome-ready.
Example 1
- Input:
- s = "aba"
- Output:
- 4
"a", "b", "a" and "aba". "ab" and "ba" have two odd letters.
Example 2
- Input:
- s = "aabb"
- Output:
- 9
The 4 single letters, "aa", "bb", "aab", "abb" and "aabb".
Constraints
- 1 ≤ s.length ≤ 10^5
- s contains only letters from 'a' to 'j'.
Hint
Show the first hint
Only the parity (odd/even) of each letter's count matters. How can you describe the parities of all 10 letters at once?
Walkthrough
How to approach it
01Clarify before coding
- Are substrings counted by position, so equal strings at different places count twice? Yes.
- Is the alphabet really only a–j? Yes, which keeps the mask at 10 bits (1024 states).
- Does a single letter count? Yes, one odd letter is allowed.
02Brute force
For each start, extend the end while maintaining letter parities and the number of odd letters; count when that number is ≤ 1.
Cost: O(n²) time: 5·10^9 steps for n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.