Problem overview
The method CheckInclusion receives two strings of lowercase letters, s1 and s2. It returns true when some substring of s2 is a permutation of s1: a run of consecutive letters of s2, exactly as long as s1, that holds every letter as many times as s1 does, in any order.
For s1 = "ab" and s2 = "eidbaooo" the answer is true, because s2 contains "ba". For s2 = "eidboaoo" it is false: there is an a and a b, but never next to each other. For s1 = "adc" and s2 = "dcda" it is true: the last three letters, "cda", hold one a, one c and one d.
Approach: a window that counts letters
The direct way is to check every substring of s2 of length s1.Length on its own, counting its letters from scratch. That takes O(n * m) time, where n is the length of s2 and m the length of s1. Both can reach 100,000, which is too slow.
Notice that two neighbouring windows share almost all their letters. When the window slides one step to the right, one letter comes in on the right and one leaves on the left. So there is no need to recount: update the counts for those two letters only.
The lesson keeps an array need of 26 counts, one per letter. need[0] says how many more as the window still needs, need[1] the bs, and so on. At the start the window is empty, so need holds the letter counts of s1. A letter entering the window lowers its count; a letter leaving raises it. A second number, missing, tracks how many letters of s1 the window still lacks in total. It starts at s1.Length, and when it reaches 0 the window holds everything s1 has. Since the window is never longer than s1, there is no room for anything else, so it is a permutation.
The count in need can go below 0: the window then holds more of that letter than s1 has. Those extra copies must not lower missing, which is why the code only does missing-- when the count was above 0.
Here is the run for s1 = "adc" and s2 = "dcda":
last=0 in d missing=2
last=1 in c missing=1
last=2 in d missing=1
last=3 in a out d missing=0
-> true
The second d was an extra copy, so missing stayed at 1. At last=3 the first d leaves and the a comes in, so the window is "cda" and nothing is missing.
Step by step
- Create
needwithnew int[26]. A newintarray is filled with zeros. - Count the letters of
s1with aforeachover its characters, and add 1 toneed[c - 'a']for each. Acharis a number, its code, andatozhave consecutive codes, soc - 'a'is 0 fora, 1 forband so on. - Set
missingtos1.Length. - Slide the window with a loop over
last, the index of the letter that enters on the right. - Find the letter's number:
code = s2[last] - 'a'. - Update
missingfirst: ifneed[code]is above 0, the window needed this letter, somissing--. At 0 or below, the copy is extra andmissingstays. - Then lower
need[code]by one: the window holds one more of this letter. - Drop the oldest letter when the window is too long. If
last >= s1.Length, the window is one letter longer thans1. The letter that leaves iss2[last - s1.Length]. - Undo its effect: raise
need[oldCode]by one. If the count is now above 0, the window lost a letter thats1needs, somissing++. If it is still 0 or below, the window had a spare copy and lost nothing. - Check for a match: if
missing == 0, returntrue. In the first turns the window is shorter thans1, so it can't hold all its letters yet. - After the loop, return
false.
The solution in C#
class Solution {
public bool CheckInclusion(string s1, string s2) {
int[] need = new int[26];
foreach (char c in s1) {
need[c - 'a']++;
}
int missing = s1.Length;
for (int last = 0; last < s2.Length; last++) {
int code = s2[last] - 'a';
if (need[code] > 0) missing--;
need[code]--;
if (last >= s1.Length) {
int oldCode = s2[last - s1.Length] - 'a';
need[oldCode]++;
if (need[oldCode] > 0) missing++;
}
if (missing == 0) return true;
}
return false;
}
}
The C# details worth knowing:
- Subtracting chars gives an
int.c - 'a'has typeint, so it can index the array directly, with no cast. - Strings are indexable.
s2[last]returns achar. Strings are immutable, so the code never changes them and never builds substrings: slicing withSubstringinside the loop would copy letters and bring back the O(n * m) cost. need[c - 'a']++is a single statement that reads, adds one and writes back. The same works for--and for entries of an array.- Bounds are checked. A character outside
atoz, such as an uppercase letter, would give an index below 0 or above 25 and throw anIndexOutOfRangeException. The problem promises lowercase letters only. - Single-line
if. A statement without braces is legal for one statement, as inif (missing == 0) return true;. Adding braces is a safe habit when you later add a second line.
Complexity
Time: O(n + m). Counting the letters of s1 takes m steps. The window loop runs n times, and each turn does a constant amount of work: each letter of s2 comes into the window once and leaves it once.
Space: O(1). The array has 26 entries whatever the input length.
Edge cases and common mistakes
s1longer thans2."abc"in"ab"returnsfalse. The window never gets enough letters, somissingnever reaches 0, and the finalreturn falsecovers it.- Repeated letters.
"aab"in"abab"returnstrue("aba"has twoas and ab), while"aab"in"abcb"returnsfalse. A plain "is this letter ins1?" check would not tell these apart; the counts do. - Same length.
"abc"in"abc"returnstrue. The window never needs to slide off a letter, andlast >= s1.Lengthis never true. - One letter.
"a"in"a"returnstrue. - Lowering
missingfor extra copies. Ifmissing--ran for every letter that enters, a window with a repeated letter, such as"aab"against a window"abb", could reach 0 without being a permutation. The checkneed[code] > 0is what stops it. - Updating in the wrong order. Lowering
need[code]before testing it makes the test compare the wrong value. Test first, then lower. - Forgetting to remove the old letter. The window would grow past the length of
s1, and a window that is too long can't be a permutation.
Testing
"ab"in"eidbaooo"givestrue."ab"in"eidboaoo"givesfalse."adc"in"dcda"givestrue."abc"in"ab"givesfalse."a"in"a"givestrue."aab"in"abab"givestrue."aab"in"abcb"givesfalse."abc"in"abc"givestrue.
