567. Permutation in String

Description

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

Constraints

• 1 <= s1.length, s2.length <= 104

• s1 and s2 consist of lowercase English letters.

Approach

Links

• Binarysearch

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: s1 = "ab", s2 = "eidbaooo"

Output: true

Explanation: s2 contains one permutation of s1 ("ba").

Example 2

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : O(1)
 */

class Solution {
    
    public boolean checkInclusion(String s1, String s2) {
        int[] counter = new int[26];
        
        for(char ch: s1.toCharArray()) {
            counter[ch-'a']++;
        }
        
        int s1Len = s1.length(), s2Len = s2.length();
        
        for(int i = 0; i < s2Len; i++) {
            char ch = s2.charAt(i);
            counter[ch-'a']--;
            
            if(i >= s1Len) {
                counter[s2.charAt(i-s1Len) - 'a']++;
            }
            if(isPermutation(counter)) {
                return true;
            }
        }
        return false;
    }
    
    private boolean isPermutation(int[] counter) {
        for(int i = 0; i < 26; i++) {
            if(counter[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

Follow up