Permutation in String

Medium

Python

def check_inclusion(s1,s2):
    from collections import Counter
    need=Counter(s1); window=Counter()
    l=0
    for r,c in enumerate(s2):
        window[c]+=1
        if r>=len(s1)-1:
            if window==need: return True
            window[s2[l]]-=1
            if window[s2[l]]==0: del window[s2[l]]
            l+=1
    return False

Java

public boolean checkInclusion(String s1,String s2){
    int[] need=new int[26],window=new int[26];
    for(char c:s1.toCharArray()) need[c-'a']++;
    int l=0;
    for(int r=0;r<s2.length();r++){
        window[s2.charAt(r)-'a']++;
        if(r>=s1.length()-1){
            if(Arrays.equals(window,need)) return true;
            window[s2.charAt(l++)-'a']--;
        }
    } return false;
}

Key Insight

Same as find anagrams but returns bool. Counter equality vs Arrays.equals().

Python → Java Differences

Counter==Counter vs Arrays.equals()
int[26] efficient for lowercase
Fixed window identical

Python

def check_inclusion(s1,s2):
    from collections import Counter
    need=Counter(s1); window=Counter()
    l=0
    for r,c in enumerate(s2):
        window[c]+=1
        if r>=len(s1)-1:
            if window==need: return True
            window[s2[l]]-=1
            if window[s2[l]]==0: del window[s2[l]]
            l+=1
    return False

Java

public boolean checkInclusion(String s1,String s2){
    int[] need=new int[26],window=new int[26];
    for(char c:s1.toCharArray()) need[c-'a']++;
    int l=0;
    for(int r=0;r<s2.length();r++){
        window[s2.charAt(r)-'a']++;
        if(r>=s1.length()-1){
            if(Arrays.equals(window,need)) return true;
            window[s2.charAt(l++)-'a']--;
        }
    } return false;
}

Algorithm Steps

1. Fixed window
2. Compare at each position

← Previous All Sliding Window Next →