LeetCode [567] Permutation in String

567. Permutation in String

Medium

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

 

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:

• The input strings only contain lower case letters.
• The length of both given strings is in range [1, 10,000].

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

class Solution { public: bool checkInclusion(string s1, string s2) { int mp1[256] = {0}, mp2[256] = {0}; int n1 = s1.size(), n2 = s2.size(), cnt = 0, i = 0, j = 0; for(auto c:s1) mp1[c]++; while(j<n2){ while(j-i+1>n1){ if(--mp2[s2[i]]<mp1[s2[i]]) cnt--; i++; } if(++mp2[s2[j]]<=mp1[s2[j]]) cnt++; if(cnt==n1) return true; j++; } return false; } }; class Solution { public: bool checkInclusion(string s1, string s2) { int sz1 = s1.size(), sz2 = s2.size(); if(sz1>sz2) return false; vector<int> count(26), zeros(26, 0); for(int i=0; i<sz1; ++i) { count[s1[i]-'a']--; count[s2[i]-'a']++; } if(count == zeros) return true; for(int i=sz1; i<sz2; ++i){ count[s2[i-sz1]-'a']--; count[s2[i]-'a']++; if(count == zeros) return true; } return false; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

//Java class Solution { public boolean checkInclusion(String s1, String s2) { int n1 = s1.length(), n2 = s2.length(); int[] cnt1 = new int[256], cnt2 = new int[256]; for(char c:s1.toCharArray()){ cnt1[c]++; } int i = 0, j = 0, len = 0; while(j<n2){ while(j-i+1>n1){ char c = s2.charAt(i++); if(cnt2[c]<=cnt1[c]){ len--; } cnt2[c]--; } char c = s2.charAt(j++); ++cnt2[c]; if(cnt2[c]<=cnt1[c]){ len++; } if(len==n1){ return true; } } return false; } }