Last updated on February 28th, 2025 at 01:29 pm

Here, we see a Permutation in String LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Sliding Window, Two Pointers

Companies

Microsoft

Level of Question

Medium

Permutation in String LeetCode Solution

1. Problem Statement

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.

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

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is Sliding Window. This pattern is commonly used for problems involving contiguous subarrays or substrings, where the goal is to find a specific property (e.g., matching a permutation, sum, or other criteria) within a sliding window of fixed size.

3. Code Implementation in Different Languages

3.1 Permutation in String C++

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
	    vector<int> cur(26), goal(26);
	    for(char c : s1) goal[c - 'a']++;
	    for(int i = 0; i < s2.size(); i++) {
		    cur[s2[i] - 'a']++;
		    if(i >= s1.size()) cur[s2[i - s1.size()] - 'a']--;
		    if(goal == cur) return true;
	    }
	    return false;        
    }
};

3.2 Permutation in String Java

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

3.3 Permutation in String JavaScript

var checkInclusion = function (s1, s2) {
    const len1 = s1.length, len2 = s2.length;
    if (len1 > len2) return false;
    const count = Array(26).fill(0);
    for (let i = 0; i < len1; i++) {
        count[s1.charCodeAt(i)-97]++;
        count[s2.charCodeAt(i)-97]--;
    }
    if (!count.some(e => e !== 0)) return true;
    for (let i = len1; i < len2; i++) {
        count[s2.charCodeAt(i)-97]--;
        count[s2.charCodeAt(i-len1)-97]++;
        if (!count.some(e => e !== 0)) return true;
    }
    return false;
};

3.4 Permutation in String Python

class Solution(object):
    def checkInclusion(self, s1, s2):
        window = len(s1)
        s1_c = Counter(s1)
        for i in range(len(s2)-window+1):
            s2_c = Counter(s2[i:i+window])
            if s2_c == s1_c:
                return True
        return False

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n + m)	O(1)
Java	O(n + m)	O(1)
JavaScript	O(n + m)	O(1)
Python	O(n + m)	O(n)