Algorithm
Problem Name: 567. Permutation in String
Problem Link: https://leetcode.com/problems/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 <= 104s1ands2consist of lowercase English letters.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
bool checkInclusion(char* s1, char* s2) {
int cnt[26] = { 0 };
int total = 0;
int i, j;
char c, k;
while (c = *(s1 ++)) {
c -= 'a';
cnt[c] ++;
total ++;
}
i = j = 0;
while (c = s2[j ++]) {
c -= 'a';
if (cnt[c] > 0) total --;
if (total == 0) return true; // where i is the start index, j - i is the length
cnt[c] --;
while (cnt[c] < 0) {
k = s2[i ++];
k -= 'a';
cnt[k] ++;
if (cnt[k] > 0) total ++;
}
}
return false;
}
Input
s1 = "ab", s2 = "eidbaooo"
Output
true
#2 Code Example with C++ Programming
Code -
C++ Programming
start coding...
class Solution {
public:
bool checkInclusion(string s1, string s2) {
int count = s1.size();
unordered_map < char, int>m;
for(auto c: s1) m[c]++;
int l = 0, r = 0;
while(r < s2.size()){
if(m[s2[r++]]-- > 0) count--;
while(count == 0){
if(r - l == s1.size()) return true;
if(m[s2[l++]]++ == 0) count++;
}
}
return false;
}
};
Input
s1 = "ab", s2 = "eidbaooo"
Output
true
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s2.length() < s1.length()) {
return false;
}
int[] frequency = new int[26];
for (int i = 0; i < s1.length(); i++) {
frequency[s1.charAt(i) - 'a']++;
frequency[s2.charAt(i) - 'a']--;
}
if (allZeroArray(frequency)) {
return true;
}
for (int i = s1.length(); i < s2.length(); i++) {
frequency[s2.charAt(i) - 'a']--;
frequency[s2.charAt(i - s1.length()) - 'a']++;
if (allZeroArray(frequency)) {
return true;
}
}
return false;
}
private boolean allZeroArray(int[] frequency) {
for (int count : frequency) {
if (count != 0) {
return false;
}
}
return true;
}
}
Input
s1 = "ab", s2 = "eidboaoo"
Output
false
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const checkInclusion = function(s1, s2) {
if(s1.length > s2.length) return false
const s1map = new Array(26).fill(0)
const s2map = new Array(26).fill(0)
const aCode = ('a').charCodeAt(0)
const zCode = ('z').charCodeAt(0)
for(let i = 0; i < s1.length; i++) {
s1map[s1.charCodeAt(i) - aCode]++
s2map[s2.charCodeAt(i) - aCode]++
}
for(let i = 0; i < s2.length - s1.length; i++) {
if(matches(s1map, s2map)) return true
s2map[s2.charCodeAt(i + s1.length) - aCode]++
s2map[s2.charCodeAt(i) - aCode]--
}
return matches(s1map, s2map)
};
function matches(s1map, s2map) {
for(let i = 0; i < 26; i++) {
if(s1map[i] !== s2map[i]> return false
}
return true
}
Input
s1 = "ab", s2 = "eidboaoo"
Output
false
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def checkInclusion(self, s1, s2):
if len(s1) > len(s2): return False
dic = collections.defaultdict(int)
for i in range(len(s1)):
dic[s1[i]] += 1
if dic[s1[i]] == 0: del dic[s1[i]]
dic[s2[i]] -= 1
if dic[s2[i]] == 0: del dic[s2[i]]
i = 0
for j in range(len(s1), len(s2)):
if not dic: return True
dic[s2[j]] -= 1
if dic[s2[j]] == 0: del dic[s2[j]]
dic[s2[i]] += 1
if dic[s2[i]] == 0: del dic[s2[i]]
i += 1
return not dic
Input
s1 = "ab", s2 = "eidbaooo"
Output
true
#6 Code Example with C# Programming
Code -
C# Programming
using System.Linq;
namespace LeetCode
{
public class _0567_PermutationInString
{
public bool CheckInclusion(string s1, string s2)
{
var s1Length = s1.Length;
var s2Length = s2.Length;
if (s1Length > s2Length) return false;
var s1Count = new int[26];
foreach (var ch in s1)
s1Count[ch - 'a']++;
var s2Count = new int[26];
for (int i = 0; i < s2Length; i++)
{
s2Count[s2[i] - 'a']++;
if (i >= s1Length)
s2Count[s2[i - s1Length] - 'a']--;
if (s2Count.SequenceEqual(s1Count))
return true;
}
return false;
}
}
}
Input
s1 = "ab", s2 = "eidbaooo"
Output
true