Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Count substrings that are 'special palindromes': either (a) all characters identical, or (b) all identical except a single different middle character. Run-length-encode the string into (char, count) runs. Type (a) contributes L·(L+1)/2 per run of length L. Type (b): for each single-character run (count == 1) whose neighbours are the same character, add min(left run length, right run length). Sum both. O(n) time, O(n) space.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you compress the string into runs and translate the two special-palindrome shapes into closed-form counts, avoiding the naive O(n²) (or worse) substring enumeration.
Where candidates slip
Counting type (b) with the wrong bound (using the middle or the larger neighbour instead of min of the two flanks), or requiring the middle run to be a single char but forgetting to check the neighbours are the same character.
How to stand out
Derive both formulas out loud: triangular number for all-same runs, and min(left,right) for a one-character separator between two equal-character runs. State it's a single O(n) pass after RLE.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewString sneighbours same char?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Check Every Substring (Brute Force)
1Hint 1Explore hintHide hint
A substring is special if it's all one char, or all one char with a single different middle. How would you verify one substring?
2Hint 2Explore hintHide hint
Enumerate all O(n²) substrings; for each, check the special condition in O(n).
3Hint 3Explore hintHide hint
That's O(n³) — fine for tiny inputs only. Note the run structure to do better.
A · Core idea
The definitional approach: generate every substring and test whether it is a special palindrome (all same, or all same with one differing middle character), incrementing a counter on each success.
Why it's correct. It checks the literal definition on every candidate, so it can't miss any.
Why it's unusable. With n up to 10⁶ there are ~5·10¹¹ substrings — enumerating them is impossible, let alone validating each. The structure to exploit: special palindromes are entirely determined by runs of identical characters. Compressing to runs reduces the problem to a couple of arithmetic formulas over at most n runs.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = "aaa"Array state
[0..2]
"aaa" all same → special
6C · Code with teaching comments
Reference implementation previewpublic long substrCount(int n, String s) { long count = 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if (isSpecial(s, i, j)) count++;Explore the full codeHide the full code
D · Why it works and complexityO(n³) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Both special-palindrome shapes are functions of run boundaries, not of individual character positions. Once you see that, the O(n²) substring space collapses to an O(n) walk over runs.
ComplexityO(n³) time, O(1) space — There are O(n²) substrings and validating each is O(n) → O(n³). Even with an O(1) incremental check it's O(n²), still hopeless at n = 10⁶.
E · Edge cases and pitfalls5s = "a" — One substring, all same → 1.Explore edge casesHide edge cases
Edge cases handled
s = "a"One substring, all same → 1.s = "ab""a","b" special; "ab" not → 2.
Pitfalls
- O(n²)/O(n³) is impossible at n = 10⁶.
- Treating even-length one-odd-middle as valid (shape two must be odd length).
- Re-scanning each substring instead of using run structure.
Approach 2 of 2 · Optimal
Run-Length Encoding with Closed-Form Counts (Optimal)
1Hint 1Explore hintHide hint
Compress s into runs of identical characters: e.g. "aaabb" → [(a,3),(b,2)].
2Hint 2Explore hintHide hint
All-same substrings inside a run of length L number L·(L+1)/2 (choose any start≤end within the run).
3Hint 3Explore hintHide hint
For the 'one odd middle' shape, look at single-character runs whose left and right runs are the same character; they contribute min(leftLen, rightLen).
A · Core idea
Run-length-encode s into a list of (char, count) runs, then count the two shapes with arithmetic.
Type (a) — all identical. Any substring lying entirely within a run of L equal characters is all-same. The number of substrings of a length-L block is 1 + 2 + … + L = L·(L+1)/2 (pick any start, any later-or-equal end). Sum that over all runs.
Type (b) — one differing middle. This shape is XX…X Y XX…X with equal arms of X around a single Y. In RLE terms that's a single-character run (Y, 1) whose left and right neighbour runs share the same character X. The palindrome must extend equally on both sides of Y, so its arm length can be at most the shorter of the two flanking runs — giving exactly min(leftLen, rightLen) distinct special palindromes centred on that Y (arm length 1, 2, …, up to the min).
Why the middle run must be length 1. Shape two allows only a single odd character. A middle run of length ≥ 2 would put two non-X characters in the centre, which no special palindrome permits.
Why `min(left, right)` and not the middle or the max. The arms must be equal length and made entirely of X. You can grow each arm only as far as its run lasts; the shorter run is the binding constraint, so the count of valid arm lengths is min(leftLen, rightLen).
Why O(n). One pass builds the runs; one more pass counts. No substring is ever materialized or rescanned.
Why 64-bit. Triangular numbers over runs summing across 10⁶ characters can exceed the 32-bit range — accumulate in long.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = "mnonopoo"Array state
runs
m1 n1 o1 n1 o1 p1 o2
12C · Code with teaching comments
D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
RLE is the right lens whenever a substring property depends only on blocks of identical characters and their single-character separators. The two formulas — triangular number per block, min(neighbours) per lone separator — are a reusable template for 'count special-shaped substrings' problems.
ComplexityO(n) time, O(n) space — Building the run list is one O(n) pass. Summing triangular numbers and scanning runs for type (b) is O(number of runs) ≤ O(n). Total O(n) time; the run list is O(n) space.
E · Edge cases and pitfalls6s = "aaaa" — One run a4 → 4·5/2 = 10; no type (b) → 10.Explore edge casesHide edge cases
Edge cases handled
s = "aaaa"One run a4 → 4·5/2 = 10; no type (b) → 10.s = "abcbaba"Seven 1-runs → 7; type (b): c(b,b), a(b,b), b(a,a) → 3 → 10.s = "aadaa"Runs a2,d1,a2 → type (a) 3+1+3=7; type (b) d between a,a → min(2,2)=2 → 9.
Pitfalls
- Using max or the middle length instead of min(left, right) for type (b).
- Forgetting the middle run must be exactly one character.
- Accumulating in 32-bit and overflowing for large n.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic long substrCount(int n, String s) { List<int[]> runs = new ArrayList<>(); int i = 0; while (i < n) { int j = i;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Wrong bound for shape two
A shape-two palindrome grows equally on both sides of the single middle char, so it's capped by the SHORTER flanking run. Using the larger run (or the middle) overcounts.
Explore the code comparisonHide the code comparison
Wrong bound for shape two
A shape-two palindrome grows equally on both sides of the single middle char, so it's capped by the SHORTER flanking run. Using the larger run (or the middle) overcounts.
Don't write this
total += max(runs[k - 1][1], runs[k + 1][1])Write this instead
total += min(runs[k - 1][1], runs[k + 1][1])2Middle run longer than one
Shape two permits exactly one odd character. A middle run of length ≥ 2 means two non-matching characters in the centre, which is never a special palindrome.
Explore the code comparisonHide the code comparison
Middle run longer than one
Shape two permits exactly one odd character. A middle run of length ≥ 2 means two non-matching characters in the centre, which is never a special palindrome.
Don't write this
if runs[k - 1][0] == runs[k + 1][0]:
total += min(runs[k - 1][1], runs[k + 1][1])Write this instead
if runs[k][1] == 1 and runs[k - 1][0] == runs[k + 1][0]:
total += min(runs[k - 1][1], runs[k + 1][1])3Integer overflow on the total
Triangular numbers summed over n = 10⁶ can exceed 2³¹. Accumulate in a 64-bit integer.
Explore the code comparisonHide the code comparison
Integer overflow on the total
Triangular numbers summed over n = 10⁶ can exceed 2³¹. Accumulate in a 64-bit integer.
Don't write this
int total = 0;
total += len * (len + 1) / 2;Write this instead
long total = 0;
total += len * (len + 1) / 2;Revise
Carry the pattern into the interview
Pattern to remember
Run-length encoding + two counting rules
Code pattern to memorize
runs = RLE(s) # list of (char, count)
total = sum(L*(L+1)//2 for (_, L) in runs) # type (a)
for i in 1..len(runs)-2:
if runs[i].count == 1 and runs[i-1].char == runs[i+1].char:
total += min(runs[i-1].count, runs[i+1].count) # type (b)
return totalRules to remember
- 1Type (a): a run of L equal chars yields
L·(L+1)/2all-same substrings (sum 1..L). - 2Type (b) needs the middle run to be exactly one character (
count == 1). - 3Type (b) requires the left and right neighbour runs to be the same character.
- 4Type (b) contributes
min(left.count, right.count)— limited by the shorter flanking run. - 5Single-character runs as the middle are the only valid 'odd one out'; longer middles can't center a special palindrome.
Use this pattern when
- Count substrings defined by adjacency/run structure rather than arbitrary content
- Same-character runs and their single-char separators drive the answer
- An O(n) RLE pass replaces an O(n²) substring enumeration
- Palindrome-like structure that's really 'a block of one char, maybe split by one other'
Choose another pattern when
- General palindromic substrings (any content) → expand-around-center / Manacher, not RLE
- Order-independent counts → frequency map, not runs
- Substrings must be contiguous AND arbitrary → different DP
- You need the substrings themselves, not the count → enumerate explicitly
Interview takeaway
Run-length encoding turns this into arithmetic over runs. All-same substrings come from the triangular number of each run; the 'one odd middle' palindromes come from single-char runs flanked by equal characters, bounded by the shorter neighbour. No O(n²) scan needed.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternRun-length encoding plus closed-form counting. When substring counts depend only on blocks of identical characters and lone separators, compress to runs and replace O(n²) enumeration with arithmetic: triangular numbers for solid blocks, min(left,right) for a single odd middle between equal neighbours.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Count Number of Homogenous SubstringsComing soonJust the type (a) part — sum L·(L+1)/2 over runs.
- Palindromic SubstringsComing soonGeneral palindromes (any content) → expand around centers, not RLE.
- Longest Palindromic SubstringComing soonExpand-around-center; RLE doesn't capture arbitrary palindromes.
- Count Substrings with Only One Distinct LetterComing soonExactly the type (a) triangular-number count over runs.