Permutation in String

NeetCode: Permutation in String · LeetCode: 567. Permutation in String · Difficulty: Medium

Given strings s1 and s2, return true if s2 contains a substring that is a permutation of s1. Both contain lowercase letters.

Example

Text

Input:  s1 = "abc", s2 = "lecabee"    Output: true    ("cab")
Input:  s1 = "abc", s2 = "lecaabee"   Output: false

Brute force: sort every window

Every window of s2 with length s1.length() is compared to s1 after sorting both as char[] arrays. Arrays.equals compares two arrays element by element (== on arrays compares references).

Java

import java.util.Arrays;

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length();
        if (n > s2.length()) {
            return false;
        }
        char[] target = s1.toCharArray();
        Arrays.sort(target);
        for (int start = 0; start + n <= s2.length(); start++) {
            char[] window = s2.substring(start, start + n).toCharArray();
            Arrays.sort(window);
            if (Arrays.equals(window, target)) {
                return true;
            }
        }
        return false;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.checkInclusion("abc", "lecabee"));
        System.out.println(s.checkInclusion("abc", "lecaabee"));
    }
}

Output

true
false

Time: O(m · n log n). Space: O(n).

Optimal: fixed-size window of letter counts

A permutation has the same letter counts as s1. s.charAt(i) - 'a' is the int index 0 to 25 of a lowercase letter. Compare a 26-slot count array for the current window with the one for s1. Sliding the window one step adds the new right letter and removes the old left letter, an O(1) update. Comparing two 26-element arrays with Arrays.equals is also constant time.

Java

import java.util.Arrays;

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length();
        if (n > s2.length()) {
            return false;
        }
        int[] need = new int[26];
        int[] window = new int[26];
        for (int i = 0; i < n; i++) {
            need[s1.charAt(i) - 'a']++;
            window[s2.charAt(i) - 'a']++;
        }
        if (Arrays.equals(need, window)) {
            return true;
        }
        for (int right = n; right < s2.length(); right++) {
            window[s2.charAt(right) - 'a']++;
            window[s2.charAt(right - n) - 'a']--;
            if (Arrays.equals(need, window)) {
                return true;
            }
        }
        return false;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.checkInclusion("abc", "lecabee"));
        System.out.println(s.checkInclusion("abc", "lecaabee"));
        System.out.println(s.checkInclusion("ab", "a"));
    }
}

Output

true
false
false

Time: O(m) for s2 of length m (with a 26-element compare per step). Space: O(1).