Permutation in String

Share

Given two strings s1 and s2 of lowercase letters, return true if s2 contains a permutation of s1 as a substring. This is LeetCode 567.

Example 1
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains "ba".
Example 2
Input: s1 = "ab", s2 = "eidboaoo"
Output: false

How to Think About It

Step 1: What a permutation means here

A substring is a permutation of s1 when it has the same length and the same count of every letter. Order does not matter.

Step 2: Slide a window of length n = s1.length()

Only substrings of length n can qualify, so slide a fixed-size window across s2. Each step, one letter enters and one leaves.

Step 3: Track the difference, not two count arrays

Keep diff[c] = (count of c in s1) minus (count of c in the window). The window is a permutation when all 26 entries are 0.

Comparing all 26 entries at every step would work, but we can do better: keep zeros, the number of entries that are 0. Each step changes only two entries, and each change can only move zeros by one. The window matches when zeros == 26.

Walkthrough

s1 = "ab", s2 = "eidbaooo", window length 2. The table shows only the letters a and b in diff; every other letter is 0 once it has left the window.

Windowdiff[a]diff[b]Other letters all 0?Match?
ei11no (e, i are -1)no
id11nono
db10no (d is -1)no
ba00yesyes: return true

Java Solution

The helper change updates one entry and reports whether that entry became 0 (+1), stopped being 0 (-1), or neither (0).

Java
public class PermutationInString {

    public static boolean checkInclusion(String s1, String s2) {
        int n = s1.length();
        if (n > s2.length()) {
            return false;
        }
        int[] diff = new int[26];             // count in s1 minus count in the window
        for (int i = 0; i < n; i++) {
            diff[s1.charAt(i) - 'a']++;
            diff[s2.charAt(i) - 'a']--;
        }
        int zeros = 0;                        // letters whose counts match
        for (int d : diff) {
            if (d == 0) {
                zeros++;
            }
        }
        for (int i = n; ; i++) {
            if (zeros == 26) {
                return true;                  // the window is a permutation of s1
            }
            if (i == s2.length()) {
                return false;
            }
            zeros += change(diff, s2.charAt(i) - 'a', -1);      // letter enters the window
            zeros += change(diff, s2.charAt(i - n) - 'a', +1);  // letter leaves the window
        }
    }

    // Apply delta to diff[c]; return how the number of zero entries changed (-1, 0 or +1)
    private static int change(int[] diff, int c, int delta) {
        int before = diff[c] == 0 ? 1 : 0;
        diff[c] += delta;
        int after = diff[c] == 0 ? 1 : 0;
        return after - before;
    }

    public static void main(String[] args) {
        System.out.println(checkInclusion("ab", "eidbaooo"));   // true
        System.out.println(checkInclusion("ab", "eidboaoo"));   // false
    }
}

The original implementation, PermutationInString.java, is on GitHub.

Complexity
  • Time: O(n + m): constant work per step.
  • Space: O(1): 26 counters.

To list every match instead of stopping at the first, see Find All Anagrams in a String.