567. Permutation in String LeetCode Solution

In this guide, you will get 567. Permutation in String LeetCode Solution with the best time and space complexity. The solution to Permutation in String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Permutation in String solution in C++
Permutation in String solution in Java
Permutation in String solution in Python
Additional Resources

567. Permutation in String LeetCode Solution image

Problem Statement of Permutation in String

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

Constraints:

1 <= s1.length, s2.length <= 104
s1 and s2 consist of lowercase English letters.

Complexity Analysis

Time Complexity: O(|\texttt{s1}| + |\texttt{s2}|)
Space Complexity: O(128) = O(1)

567. Permutation in String LeetCode Solution in C++

class Solution {
 public:
  bool checkInclusion(string s1, string s2) {
    vector<int> count(26);
    int required = s1.length();

    for (const char c : s1)
      ++count[c - 'a'];

    for (int l = 0, r = 0; r < s2.length(); ++r) {
      if (--count[s2[r] - 'a'] >= 0)
        --required;
      while (required == 0) {
        if (r - l + 1 == s1.length())
          return true;
        if (++count[s2[l++] - 'a'] > 0)
          ++required;
      }
    }

    return false;
  }
};
/* code provided by PROGIEZ */

567. Permutation in String LeetCode Solution in Java

class Solution {
  public boolean checkInclusion(String s1, String s2) {
    int[] count = new int[26];
    int required = s1.length();

    for (final char c : s1.toCharArray())
      ++count[c - 'a'];

    for (int l = 0, r = 0; r < s2.length(); ++r) {
      if (--count[s2.charAt(r) - 'a'] >= 0)
        --required;
      while (required == 0) {
        if (r - l + 1 == s1.length())
          return true;
        if (++count[s2.charAt(l++) - 'a'] > 0)
          ++required;
      }
    }

    return false;
  }
}
// code provided by PROGIEZ

567. Permutation in String LeetCode Solution in Python

class Solution {
 public:
  bool checkInclusion(string s1, string s2) {
    vector<int> count(26);
    int required = s1.length();

    for (const char c : s1)
      ++count[c - 'a'];

    for (int r = 0; r < s2.length(); ++r) {
      if (--count[s2[r] - 'a'] >= 0)
        --required;
      if (r >= s1.length())  // The window is oversized.
        if (++count[s2[r - s1.length()] - 'a'] > 0)
          ++required;
      if (required == 0)
        return true;
    }

    return false;
  }
};
 # code by PROGIEZ