567 - 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.

C++

• class Solution {
  public:
      bool checkInclusion(string s1, string s2) {
          int n = s1.size(), m = s2.size();
          if (n > m) {
              return false;
          }
          vector<int> cnt(26);
          for (int i = 0; i < n; ++i) {
              --cnt[s1[i] - 'a'];
              ++cnt[s2[i] - 'a'];
          }
          int diff = 0;
          for (int x : cnt) {
              if (x) {
                  ++diff;
              }
          }
          if (diff == 0) {
              return true;
          }
          for (int i = n; i < m; ++i) {
              int a = s2[i - n] - 'a';
              int b = s2[i] - 'a';
              if (cnt[b] == 0) {
                  ++diff;
              }
              if (++cnt[b] == 0) {
                  --diff;
              }
              if (cnt[a] == 0) {
                  ++diff;
              }
              if (--cnt[a] == 0) {
                  --diff;
              }
              if (diff == 0) {
                  return true;
              }
          }
          return false;
      }
  };

PYTHON

• class Solution:
      def checkInclusion(self, s1: str, s2: str) -> bool:
          n, m = len(s1), len(s2)
          if n > m:
              return False
          
          cnt = [0] * 26
          for i in range(n):
              cnt[ord(s2[i]) - ord('a')] += 1
              cnt[ord(s1[i]) - ord('a')] -= 1
          
          diff = sum(1 for x in cnt if x != 0)
          
          if diff == 0:
              return True
          
          for i in range(n, m):
              a = ord(s2[i - n]) - ord('a')
              b = ord(s2[i]) - ord('a')
              
              if cnt[b] == 0:
                  diff += 1
              cnt[b] += 1
              if cnt[b] == 0:
                  diff -= 1
              
              if cnt[a] == 0:
                  diff += 1
              cnt[a] -= 1
              if cnt[a] == 0:
                  diff -= 1
              
              if diff == 0:
                  return True
          
          return False

JAVA

• class Solution {
      public boolean checkInclusion(String s1, String s2) {
          int n = s1.length();
          int m = s2.length();
          if (n > m) {
              return false;
          }
          int[] cnt = new int[26];
          for (int i = 0; i < n; ++i) {
              --cnt[s1.charAt(i) - 'a'];
              ++cnt[s2.charAt(i) - 'a'];
          }
          int diff = 0;
          for (int x : cnt) {
              if (x != 0) {
                  ++diff;
              }
          }
          if (diff == 0) {
              return true;
          }
          for (int i = n; i < m; ++i) {
              int a = s2.charAt(i - n) - 'a';
              int b = s2.charAt(i) - 'a';
              if (cnt[b] == 0) {
                  ++diff;
              }
              if (++cnt[b] == 0) {
                  --diff;
              }
              if (cnt[a] == 0) {
                  ++diff;
              }
              if (--cnt[a] == 0) {
                  --diff;
              }
              if (diff == 0) {
                  return true;
              }
          }
          return false;
      }
  }