9.05Beginner / Intermediate5 topics20 min5 interactive animations

Substring basics

Substring problems: the difference between substrings and subsequences, enumerating substrings, the longest substring without repeats, the minimum window containing required letters and the longest substring replaceable by one letter. Most use a sliding window.

Learning goals

Count and enumerate substrings
Maintain a sliding window with counts or last-seen indexes
Know when the window shrinks and why the solution is linear

Prerequisites

Character patternsSliding window

9.05.1

Substrings vs subsequences

A substring is contiguous; a subsequence keeps order but may skip characters. For a string of length n there are n(n + 1)/2 non-empty substrings but 2ⁿ subsequences. “ace” is a subsequence of “abcde” but not a substring. Longest common substring and longest common subsequence are different problems with different dynamic programs.

Enumerate the substrings of a short string to see the quadratic count.

Of "abc"	Count	List
Substrings (non-empty)	6	a, ab, abc, b, bc, c
Subsequences (with empty)	8	"", a, b, c, ab, ac, bc, abc

Enumerating every substring (n(n + 1)/2 of them)

Interactive · edit the input

char[] s · length 4

0123

Current substringPalindromic substring

substrings so far

none yet

Setup

A string of length 4 has 10 non-empty substrings: 4 starting at index 0 down to 1 starting at the last index. A substring is contiguous (unlike a subsequence).

Step 1 / 12

Java

1for (int i = 0; i < s.length(); i++) {
2    for (int j = i + 1; j <= s.length(); j++) {
3        String sub = s.substring(i, j);                  // s[i .. j-1]
4        if (isPalindrome(sub)) pal.add(sub);             // optional filter
5    }
6}

Live state

0 substrings

No condition evaluated on this step

Execution trace (dry run table)Show 12 steps

Step	Line	State	What happens
1	L1		A string of length 4 has 10 non-empty substrings: 4 starting at index 0 down to 1 starting at the last index. A substring is contiguous (unlike a subsequence).
2	L3	i=0 j=1 substring="a"	s.substring(0, 1) = "a".
3	L3	i=0 j=2 substring="ab"	s.substring(0, 2) = "ab".
4	L3	i=0 j=3 substring="abb"	s.substring(0, 3) = "abb".
5	L3	i=0 j=4 substring="abba"	s.substring(0, 4) = "abba".
6	L3	i=1 j=2 substring="b"	s.substring(1, 2) = "b".
7	L3	i=1 j=3 substring="bb"	s.substring(1, 3) = "bb".
8	L3	i=1 j=4 substring="bba"	s.substring(1, 4) = "bba".
9	L3	i=2 j=3 substring="b"	s.substring(2, 3) = "b".
10	L3	i=2 j=4 substring="ba"	s.substring(2, 4) = "ba".
11	L3	i=3 j=4 substring="a"	s.substring(3, 4) = "a".
12	L6	return=10 substrings	10 substrings = n(n + 1)/2. Each substring() copies up to n characters, so the whole enumeration is O(n³) work.

9.05.2

Enumerating substrings

Two nested loops over the start and end produce every substring. Because substring copies, listing all of them costs O(n³) character copies. When only a property matters (palindrome, distinct letters), expand or slide instead of materialising each one.

Collect only palindromic substrings in the second mode.

Java

1int n = s.length();
2for (int i = 0; i < n; i++)
3    for (int j = i + 1; j <= n; j++) {
4        String sub = s.substring(i, j);      // s[i .. j-1]
5    }

Enumerating every substring (n(n + 1)/2 of them)

Interactive · edit the input

char[] s · length 4

0123

Current substringPalindromic substring

substrings so far

none yet

Setup

A string of length 4 has 10 non-empty substrings: 4 starting at index 0 down to 1 starting at the last index. A substring is contiguous (unlike a subsequence).

Step 1 / 12

Java

1for (int i = 0; i < s.length(); i++) {
2    for (int j = i + 1; j <= s.length(); j++) {
3        String sub = s.substring(i, j);                  // s[i .. j-1]
4        if (isPalindrome(sub)) pal.add(sub);             // optional filter
5    }
6}

Live state

0 substrings

No condition evaluated on this step

Execution trace (dry run table)Show 12 steps

Step	Line	State	What happens
1	L1		A string of length 4 has 10 non-empty substrings: 4 starting at index 0 down to 1 starting at the last index. A substring is contiguous (unlike a subsequence).
2	L3	i=0 j=1 substring="a"	s.substring(0, 1) = "a".
3	L3	i=0 j=2 substring="ab"	s.substring(0, 2) = "ab".
4	L3	i=0 j=3 substring="abb"	s.substring(0, 3) = "abb".
5	L3	i=0 j=4 substring="abba"	s.substring(0, 4) = "abba".
6	L3	i=1 j=2 substring="b"	s.substring(1, 2) = "b".
7	L3	i=1 j=3 substring="bb"	s.substring(1, 3) = "bb".
8	L3	i=1 j=4 substring="bba"	s.substring(1, 4) = "bba".
9	L3	i=2 j=3 substring="b"	s.substring(2, 3) = "b".
10	L3	i=2 j=4 substring="ba"	s.substring(2, 4) = "ba".
11	L3	i=3 j=4 substring="a"	s.substring(3, 4) = "a".
12	L6	return=10 substrings	10 substrings = n(n + 1)/2. Each substring() copies up to n characters, so the whole enumeration is O(n³) work.

9.05.3

Longest unique substring

To find the longest substring without repeating characters, slide a window and remember the last index of each character. When the new character is already inside the window, move the left edge just past its previous position. Each index enters and leaves once: O(n) time, O(alphabet) space.

Try “abcdbea” to see the left edge jump.

Java

1static int lengthOfLongestSubstring(String s) {
2    int[] last = new int[128]; Arrays.fill(last, -1);      // ASCII
3    int best = 0, left = 0;
4    for (int right = 0; right < s.length(); right++) {
5        char c = s.charAt(right);
6        if (last[c] >= left) left = last[c] + 1;
7        last[c] = right;
8        best = Math.max(best, right - left + 1);
9    }
10    return best;
11}

Longest substring without repeating characters

Interactive · edit the input

char[] s · length 8

01234567

WindowBest windowWindow start jumped past a repeat

last[c]

empty

Setup

Grow a window [left, right]. When the new character already sits inside the window, move left just past its previous position.

Step 1 / 18

Java

1static int lengthOfLongestSubstring(String s) {
2    int[] last = new int[128]; Arrays.fill(last, -1);        // last index of each ASCII character
3    int best = 0, left = 0;
4    for (int right = 0; right < s.length(); right++) {
5        char c = s.charAt(right);
6        if (last[c] >= left) left = last[c] + 1;             // jump past the previous copy of c
7        last[c] = right;
8        best = Math.max(best, right - left + 1);
9    }
10    return best;
11}

Live state

left

best

No condition evaluated on this step

Execution trace (dry run table)Show 18 steps

Step	Line	State	What happens
1	L3	left=0 best=0	Grow a window [left, right]. When the new character already sits inside the window, move left just past its previous position.
2	L6	right=0 c='a' last[c]=-1 left=0	'a' is new: the window can grow.
3	L8	right=0 left=0 window=1 best=1	Window [0, 0] = "a" has length 1; best so far 1.
4	L6	right=1 c='b' last[c]=-1 left=0	'b' is new: the window can grow.
5	L8	right=1 left=0 window=2 best=2	Window [0, 1] = "ab" has length 2; best so far 2.
6	L6	right=2 c='c' last[c]=-1 left=0	'c' is new: the window can grow.
7	L8	right=2 left=0 window=3 best=3	Window [0, 2] = "abc" has length 3; best so far 3.
8	L6	right=3 c='a' last[c]=0 left=0	'a' was last seen at 0, inside the window: move left to 1.
9	L8	right=3 left=1 window=3 best=3	Window [1, 3] = "bca" has length 3; best so far 3.
10	L6	right=4 c='b' last[c]=1 left=1	'b' was last seen at 1, inside the window: move left to 2.
11	L8	right=4 left=2 window=3 best=3	Window [2, 4] = "cab" has length 3; best so far 3.
12	L6	right=5 c='c' last[c]=2 left=2	'c' was last seen at 2, inside the window: move left to 3.
13	L8	right=5 left=3 window=3 best=3	Window [3, 5] = "abc" has length 3; best so far 3.
14	L6	right=6 c='b' last[c]=4 left=3	'b' was last seen at 4, inside the window: move left to 5.
15	L8	right=6 left=5 window=2 best=3	Window [5, 6] = "cb" has length 2; best so far 3.
16	L6	right=7 c='b' last[c]=6 left=5	'b' was last seen at 6, inside the window: move left to 7.
17	L8	right=7 left=7 window=1 best=3	Window [7, 7] = "b" has length 1; best so far 3.
18	L10	return=3	Longest substring without repeats has length 3: "abc". Each index enters and leaves the window once: O(n).

9.05.4

Minimum window substring

Find the shortest substring of s that contains every letter of t, with multiplicity. Grow the right edge until the window is valid, then shrink the left edge as far as validity allows, recording the best window. A missing counter tracks how many required letters are still absent, so validity is checked in O(1). Total O(n + m).

Use the repeat preset to see why counts, not just presence, matter.

Java

1static String minWindow(String s, String t) {
2    int[] need = new int[128];
3    for (char c : t.toCharArray()) need[c]++;
4    int missing = t.length(), left = 0, bestStart = 0, bestLen = Integer.MAX_VALUE;
5    for (int right = 0; right < s.length(); right++) {
6        if (need[s.charAt(right)]-- > 0) missing--;
7        while (missing == 0) {
8            if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestStart = left; }
9            if (++need[s.charAt(left++)] > 0) missing++;
10        }
11    }
12    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
13}

Minimum window substring

Interactive · edit the input

char[] s · length 13

0123456789101112

WindowShortest valid windowAlready checked

need[c] (still required)

A:1

B:1

C:1

Setup

Find the shortest window of s containing every letter of "ABC" (with multiplicity). missing counts the required letters not yet covered.

Step 1 / 25

Java

1static String minWindow(String s, String t) {
2    int[] need = new int[128]; for (char c : t.toCharArray()) need[c]++;
3    int missing = t.length(), left = 0, bestStart = 0, bestLen = Integer.MAX_VALUE;
4    for (int right = 0; right < s.length(); right++) {
5        if (need[s.charAt(right)]-- > 0) missing--;           // a still-needed character arrived
6        while (missing == 0) {                                // window is valid: shrink from the left
7            if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestStart = left; }
8            if (++need[s.charAt(left++)] > 0) missing++;      // we dropped a needed character
9        }
10    }
11    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
12}

Live state

missing

left

No condition evaluated on this step

Execution trace (dry run table)Show 25 steps

Step	Line	State	What happens
1	L3	missing=3 left=0	Find the shortest window of s containing every letter of "ABC" (with multiplicity). missing counts the required letters not yet covered.
2	L5	right=0 c='A' missing=2	'A' was still needed: missing drops to 2.
3	L5	right=1 c='D' missing=2	'D' is not needed (or already covered): need['D'] goes negative to remember the surplus.
4	L5	right=2 c='O' missing=2	'O' is not needed (or already covered): need['O'] goes negative to remember the surplus.
5	L5	right=3 c='B' missing=1	'B' was still needed: missing drops to 1.
6	L5	right=4 c='E' missing=1	'E' is not needed (or already covered): need['E'] goes negative to remember the surplus.
7	L5	right=5 c='C' missing=0	'C' was still needed: missing drops to 0.
8	L8	left=0 window="ADOBEC" bestLen=6 missing=1	Window "ADOBEC" is valid (best 6). Drop 'A' from the left: it was needed, so missing becomes 1.
9	L5	right=6 c='O' missing=1	'O' is not needed (or already covered): need['O'] goes negative to remember the surplus.
10	L5	right=7 c='D' missing=1	'D' is not needed (or already covered): need['D'] goes negative to remember the surplus.
11	L5	right=8 c='E' missing=1	'E' is not needed (or already covered): need['E'] goes negative to remember the surplus.
12	L5	right=9 c='B' missing=1	'B' is not needed (or already covered): need['B'] goes negative to remember the surplus.
13	L5	right=10 c='A' missing=0	'A' was still needed: missing drops to 0.
14	L8	left=1 window="DOBECODEBA" bestLen=6 missing=0	Window "DOBECODEBA" is valid (best 6). Drop 'D' from the left: it was surplus, still valid.
15	L8	left=2 window="OBECODEBA" bestLen=6 missing=0	Window "OBECODEBA" is valid (best 6). Drop 'O' from the left: it was surplus, still valid.
16	L8	left=3 window="BECODEBA" bestLen=6 missing=0	Window "BECODEBA" is valid (best 6). Drop 'B' from the left: it was surplus, still valid.
17	L8	left=4 window="ECODEBA" bestLen=6 missing=0	Window "ECODEBA" is valid (best 6). Drop 'E' from the left: it was surplus, still valid.
18	L8	left=5 window="CODEBA" bestLen=6 missing=1	Window "CODEBA" is valid (best 6). Drop 'C' from the left: it was needed, so missing becomes 1.
19	L5	right=11 c='N' missing=1	'N' is not needed (or already covered): need['N'] goes negative to remember the surplus.
20	L5	right=12 c='C' missing=0	'C' was still needed: missing drops to 0.
21	L8	left=6 window="ODEBANC" bestLen=6 missing=0	Window "ODEBANC" is valid (best 6). Drop 'O' from the left: it was surplus, still valid.
22	L8	left=7 window="DEBANC" bestLen=6 missing=0	Window "DEBANC" is valid (best 6). Drop 'D' from the left: it was surplus, still valid.
23	L8	left=8 window="EBANC" bestLen=5 missing=0	Window "EBANC" is valid (best 5). Drop 'E' from the left: it was surplus, still valid.
24	L8	left=9 window="BANC" bestLen=4 missing=1	Window "BANC" is valid (best 4). Drop 'B' from the left: it was needed, so missing becomes 1.
25	L11	return="BANC"	Shortest window "BANC" (length 4). Both pointers only move right: O(n + m).

9.05.5

Character replacement window

Given at most k replacements, find the longest substring that can become one repeated letter. A window is valid when (length - count of its most frequent letter) ≤ k, because those are the letters to replace. Slide the window, keep letter counts and the largest count seen (it never needs to decrease), and shrink only when the window becomes invalid. O(n) time, O(26) space.

Change k and watch the window size respond.

Java

1static int characterReplacement(String s, int k) {
2    int[] count = new int[26];
3    int left = 0, maxFreq = 0, best = 0;
4    for (int right = 0; right < s.length(); right++) {
5        maxFreq = Math.max(maxFreq, ++count[s.charAt(right) - 'A']);
6        while (right - left + 1 - maxFreq > k) count[s.charAt(left++) - 'A']--;
7        best = Math.max(best, right - left + 1);
8    }
9    return best;
10}

Longest repeating character replacement

Interactive · edit the input

char[] s · length 7

0123456

WindowBest window

count[c] in the window

empty

Setup

A window is valid when (window length - count of its most common letter) <= k = 1: those are the letters to replace.

Step 1 / 19

Java

1static int characterReplacement(String s, int k) {
2    int[] count = new int[26];
3    int left = 0, maxFreq = 0, best = 0;
4    for (int right = 0; right < s.length(); right++) {
5        maxFreq = Math.max(maxFreq, ++count[s.charAt(right) - 'A']);
6        while (right - left + 1 - maxFreq > k)                // more than k characters to replace
7            count[s.charAt(left++) - 'A']--;
8        best = Math.max(best, right - left + 1);
9    }
10    return best;
11}

Live state

left

maxFreq

best

No condition evaluated on this step

Execution trace (dry run table)Show 19 steps

Step	Line	State	What happens
1	L3	k=1 left=0 maxFreq=0 best=0	A window is valid when (window length - count of its most common letter) <= k = 1: those are the letters to replace.
2	L5	right=0 c='A' maxFreq=1 len - maxFreq=0	Add 'A'. The most common letter appears 1 times (maxFreq never decreases: a smaller window cannot beat a past best anyway).
3	L8	left=0 right=0 best=1	Valid window "A", length 1; best 1.
4	L5	right=1 c='A' maxFreq=2 len - maxFreq=0	Add 'A'. The most common letter appears 2 times (maxFreq never decreases: a smaller window cannot beat a past best anyway).
5	L8	left=0 right=1 best=2	Valid window "AA", length 2; best 2.
6	L5	right=2 c='B' maxFreq=2 len - maxFreq=1	Add 'B'. The most common letter appears 2 times (maxFreq never decreases: a smaller window cannot beat a past best anyway).
7	L8	left=0 right=2 best=3	Valid window "AAB", length 3; best 3.
8	L5	right=3 c='A' maxFreq=3 len - maxFreq=1	Add 'A'. The most common letter appears 3 times (maxFreq never decreases: a smaller window cannot beat a past best anyway).
9	L8	left=0 right=3 best=4	Valid window "AABA", length 4; best 4.
10	L5	right=4 c='B' maxFreq=3 len - maxFreq=2	Add 'B'. The most common letter appears 3 times (maxFreq never decreases: a smaller window cannot beat a past best anyway).
11	L7	left=0 len - maxFreq=1	Too many replacements needed: drop 'A' from the left.
12	L8	left=1 right=4 best=4	Valid window "ABAB", length 4; best 4.
13	L5	right=5 c='B' maxFreq=3 len - maxFreq=2	Add 'B'. The most common letter appears 3 times (maxFreq never decreases: a smaller window cannot beat a past best anyway).
14	L7	left=1 len - maxFreq=1	Too many replacements needed: drop 'A' from the left.
15	L8	left=2 right=5 best=4	Valid window "BABB", length 4; best 4.
16	L5	right=6 c='A' maxFreq=3 len - maxFreq=2	Add 'A'. The most common letter appears 3 times (maxFreq never decreases: a smaller window cannot beat a past best anyway).
17	L7	left=2 len - maxFreq=1	Too many replacements needed: drop 'B' from the left.
18	L8	left=3 right=6 best=4	Valid window "ABBA", length 4; best 4.
19	L10	return=4	Longest window convertible to a single letter with at most 1 replacement: 4. O(n) time, O(26) space.

Practice ladder

Now try it yourself

Easy

How many substrings does a string of length 6 have?
Is "ace" a substring or a subsequence of "abcde"?

Medium

Find the longest substring without repeats in "pwwkew"
Find the minimum window of "aabdec" containing "aab"

Advanced

Explain why maxFreq never needs to decrease in the replacement window

Key takeaways

Substrings are contiguous (n(n + 1)/2); subsequences may skip (2ⁿ).
A sliding window with counts or last-seen indexes makes substring problems O(n).
Both pointers only move forward, so the total work is linear.