[Leetcode 567] Permutation in String (medium)

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

Example 1:

Input:s1 = "ab" s2 = "eidbaooo"
Output:True
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input:s1= "ab" s2 = "eidboaoo"
Output: False

Note:

1. The input strings only contain lower case letters.
2. The length of both given strings is in range [1, 10,000].

Brute force Solution

1. Get all permutations of string s1.
2. Check if each permutation is a substring of s2.

Con: Complexity is too high, performance is low.

Optimization Solution

1. String permutations are similar to anagrams.
2. String permutations have identical characters, and each character has identical occurrence.
3. 可以用hashtable来记录每个字母出现的次数. 且题目已经告知只可能存在小写字母，因此可以用一个int[26]来代替hashtable。
4. 首先遍历S1，在hashtable 中记录每个字母出现的次数。
5. 然后通过Slide Window的思路（想象成用一个长度为S1长度的窗口在S2中从左向右的滑动）。如果s2出现在当前窗口中substring，其包含的字母与s1中的字母相同，且字母出现的次数也与s2中出现的次数也相同，就说明该substring就是s1的一个permutation。

代码中

1. 滑动窗口时，用Two Pointer来指向S2当前滑动窗口的最右和最左字母。
2. 因为只采用了一个int[26]结构，且遍历s1时，tracker[s1.charAt(i) - 'a'] ++ 来记录s1中字母出现的次数。
   如何判断s2的当前substring就是s1的permutation呢？
   • 在s2中滑动窗口时，首先遍历s2中前s1长度的字符串，tracker[s2.charAt(i) - 'a'] --。遍历后，如果tracker所有entry都为0，说明s1和s2互为全排列，返回true.
   • 如果不是，那么则开始在s2中自左向右滑动窗口 （窗口长度为s1的长度），依次判断每个窗口的substring。
   • 每滑动一次，右边界右移，输入一个字符，int[26]上对应位置值-1；同时左边界也右移，减少一个字符，int[26]上对应位置值+1;
     然后判断: 此时的int[26]是否每个entry都为0。如果都为0，则说明找到了s1的permutation, return true. 否则继续向右滑动，直到遍历完S2。

image.png

Time: O(n), Space: O(1)

1. 可以用2个hashtable分别记录s1和s2 substring的字母出现次数，但凡2个hashtable相同时，则说明找到了permutation。但是需要用到2个hashtable

class Solution {
    // Solution 1: two hashmap  --- fixed length of hashmap, can use regular arraylist to replace 
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length())
        {
            return false;
        }

        int len1 = s1.length();
        int len2 = s2.length();
        int[] hashmap1 = new int[26];
        int[] hashmap2 = new int[26];

        for (int i = 0; i < len1; ++i)
        {
            hashmap1[s1.charAt(i) - 'a'] ++;
            hashmap2[s2.charAt(i) - 'a'] ++;
        
        }

        if (isSame (hashmap1, hashmap2))
        {
            return true;
        }
        
        for (int i = len1; i < s2.length(); ++i)
        {
            hashmap2[s2.charAt(i) - 'a'] ++;
            hashmap2[s2.charAt(i - len1) - 'a'] --;
            if (isSame(hashmap1, hashmap2)){

                return true;
            }
        }

        return false;
    }
    
    public boolean isSame(int[] hashmap1, int[] hashmap2)
    {
        for (int i = 0; i < hashmap1.length; ++i)
        {
            if (hashmap1[i] != hashmap2[i]){
                
                return false;
            }
        }
        
        return true;
    }
}

2. 改进：只需要一个hashtable，思路如上所述

class Solution {
    // Solution 2: one hashmap  --- fixed length of hashmap, can use regular arraylist to replace; and two pointers
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length())
        {
            return false;
        }

        int len1 = s1.length();
        int len2 = s2.length();
        
        int[] tracker = new int[26];
        
        for (int i = 0; i < len1; ++i)
        {
            tracker[s1.charAt(i) - 'a'] ++;
            tracker[s2.charAt(i) - 'a'] --;
        }
        
        if (isAllZero(tracker))
        {
            return true;
        }
        
        for (int i = len1; i < len2; ++i)
        {
            tracker[s2.charAt(i) - 'a'] --;
            tracker[s2.charAt(i - len1) - 'a'] ++;
            if (isAllZero(tracker))
            {
                return true;
            }
        }
        return false;
    }
    
    // Cannot be negative or greater than zero, otherwise it's not true
    public boolean isAllZero(int[] tracker)
    {
        for (int item : tracker)
        {
            if (item != 0)
            {
                return false;
            }
        }

        return true;
    }
}