Permutation in Given String
Program to solve Permutation in a given String Problem
You are given two strings, s1 and s2, which only contain lowercase letters.
Your task is to determine if any permutation of string s1 can be found as a substring within string s2.
In other words, you need to check if there exists a rearranged version of s1 that appears as a contiguous part of s2. If such a permutation exists, return true; otherwise, return false.
Example 1
Input: s1 = "abc", s2 = "lecabee"
Output: true
Output: true
Explanation : The substring “cab” is a permutation of “abc” and is present in “lecabee”.
Example 2
Input: s1 = "abc", s2 = "lecaabee"
Output: false
Output: false
Constraints:
- 1 <= s1.length, s2.length <= 1000
Program to solve Permutation in a given String Solution
Recommendation for Time and Space Complexity –You should aim for a solution with O(n) time and O(1) space, where n is the maximum of the lengths of the two strings.
Hints for solving problems
Hint 1 :
A brute force solution would be to check every substring of s2 with s1 by sorting s1 as well as the substring of s2. This would be an O(n^2) solution. Can you think of a better way? Maybe we can use the freqency of the characters of both the strings as we did in checking anagrams.
Hint 2 :
We return false if the length of s1 is greater than the length of s2. To count the frequency of each character in a string, we can simply use an array of size O(26), since the character set consists of a through z (26 continuous characters). Which algorithm can we use now?
There are mainly 3 approach to solve this problem-
- Brute Force Method
- Hash Table Method
- Sliding Window Method
1. Brute Force Method
Generate all permutations of the given string s1 and check if any of these permutations is a substring of s2. This method is not efficient due to the factorial time complexity.
- Time complexity: O(n^3 logn)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
bool checkInclusion(std::string s1, std::string s2) {
sort(s1.begin(), s1.end());
for (int i = 0; i < s2.length(); i++) {
for (int j = i; j < s2.length(); j++) {
string subStr = s2.substr(i, j - i + 1);
sort(subStr.begin(), subStr.end());
if (subStr == s1) {
return true;
}
}
}
return false;
}
};
Java
public class Solution {
public boolean checkInclusion(String s1, String s2) {
char[] s1Arr = s1.toCharArray();
Arrays.sort(s1Arr);
String sortedS1 = new String(s1Arr);
for (int i = 0; i < s2.length(); i++) {
for (int j = i; j < s2.length(); j++) {
char[] subStrArr = s2.substring(i, j + 1).toCharArray();
Arrays.sort(subStrArr);
String sortedSubStr = new String(subStrArr);
if (sortedSubStr.equals(sortedS1)) {
return true;
}
}
}
return false;
}
}
Python
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
s1 = sorted(s1)
for i in range(len(s2)):
for j in range(i, len(s2)):
subStr = s2[i : j + 1]
subStr = sorted(subStr)
if subStr == s1:
return True
return False
JavaScript
class Solution {
/**
* @param {string} s1
* @param {string} s2
* @return {boolean}
*/
checkInclusion(s1, s2) {
s1 = s1.split('').sort().join('');
for (let i = 0; i < s2.length; i++) {
for (let j = i; j < s2.length; j++) {
let subStr = s2.slice(i, j + 1).split('').sort().join('');
if (subStr === s1) {
return true;
}
}
}
return false;
}
}
2. Hash Table Method
Use a frequency map (hash table) for s1 and compare it with the frequency map of substrings of the same length in s2 by sliding the window.
- Time complexity: O(n*m)
- Space complexity: O(1)
where n is the length of the string1 and m is the length of string2.
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
bool checkInclusion(string s1, string s2) {
unordered_map count1;
for (char c : s1) {
count1[c]++;
}
int need = count1.size();
for (int i = 0; i < s2.length(); i++) {
unordered_map count2;
int cur = 0;
for (int j = i; j < s2.length(); j++) {
char c = s2[j];
count2[c]++;
if (count1[c] < count2[c]) {
break;
}
if (count1[c] == count2[c]) {
cur++;
}
if (cur == need) {
return true;
}
}
}
return false;
}
};
Java
public class Solution {
public boolean checkInclusion(String s1, String s2) {
Map count1 = new HashMap<>();
for (char c : s1.toCharArray()) {
count1.put(c, count1.getOrDefault(c, 0) + 1);
}
int need = count1.size();
for (int i = 0; i < s2.length(); i++) {
Map count2 = new HashMap<>();
int cur = 0;
for (int j = i; j < s2.length(); j++) {
char c = s2.charAt(j);
count2.put(c, count2.getOrDefault(c, 0) + 1);
if (count1.getOrDefault(c, 0) < count2.get(c)) {
break;
}
if (count1.getOrDefault(c, 0) == count2.get(c)) {
cur++;
}
if (cur == need) {
return true;
}
}
}
return false;
}
}
Python
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
count1 = {}
for c in s1:
count1[c] = 1 + count1.get(c, 0)
need = len(count1)
for i in range(len(s2)):
count2, cur = {}, 0
for j in range(i, len(s2)):
count2[s2[j]] = 1 + count2.get(s2[j], 0)
if count1.get(s2[j], 0) < count2[s2[j]]:
break
if count1.get(s2[j], 0) == count2[s2[j]]:
cur += 1
if cur == need:
return True
return False
JavaScript
class Solution {
/**
* @param {string} s1
* @param {string} s2
* @return {boolean}
*/
checkInclusion(s1, s2) {
let count1 = {};
for (let c of s1) {
count1[c] = (count1[c] || 0) + 1;
}
let need = Object.keys(count1).length;
for (let i = 0; i < s2.length; i++) {
let count2 = {};
let cur = 0;
for (let j = i; j < s2.length; j++) {
let c = s2[j];
count2[c] = (count2[c] || 0) + 1;
if ((count1[c] || 0) < count2[c]) {
break;
}
if ((count1[c] || 0) === count2[c]) {
cur++;
}
if (cur === need) {
return true;
}
}
}
return false;
}
}
3. Sliding Window Method
Maintain a sliding window of size equal to s1 in s2 and use two frequency arrays (or hash maps) to efficiently compare character frequencies, updating the window dynamically.
- Time complexity: O(n)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
bool checkInclusion(string s1, string s2) {
if (s1.length() > s2.length()) {
return false;
}
vector s1Count(26, 0);
vector s2Count(26, 0);
for (int i = 0; i < s1.length(); i++) {
s1Count[s1[i] - 'a']++;
s2Count[s2[i] - 'a']++;
}
int matches = 0;
for (int i = 0; i < 26; i++) {
if (s1Count[i] == s2Count[i]) {
matches++;
}
}
int l = 0;
for (int r = s1.length(); r < s2.length(); r++) {
if (matches == 26) {
return true;
}
int index = s2[r] - 'a';
s2Count[index]++;
if (s1Count[index] == s2Count[index]) {
matches++;
} else if (s1Count[index] + 1 == s2Count[index]) {
matches--;
}
index = s2[l] - 'a';
s2Count[index]--;
if (s1Count[index] == s2Count[index]) {
matches++;
} else if (s1Count[index] - 1 == s2Count[index]) {
matches--;
}
l++;
}
return matches == 26;
}
};
Java
public class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) {
return false;
}
int[] s1Count = new int[26];
int[] s2Count = new int[26];
for (int i = 0; i < s1.length(); i++) {
s1Count[s1.charAt(i) - 'a']++;
s2Count[s2.charAt(i) - 'a']++;
}
int matches = 0;
for (int i = 0; i < 26; i++) {
if (s1Count[i] == s2Count[i]) {
matches++;
}
}
int l = 0;
for (int r = s1.length(); r < s2.length(); r++) {
if (matches == 26) {
return true;
}
int index = s2.charAt(r) - 'a';
s2Count[index]++;
if (s1Count[index] == s2Count[index]) {
matches++;
} else if (s1Count[index] + 1 == s2Count[index]) {
matches--;
}
index = s2.charAt(l) - 'a';
s2Count[index]--;
if (s1Count[index] == s2Count[index]) {
matches++;
} else if (s1Count[index] - 1 == s2Count[index]) {
matches--;
}
l++;
}
return matches == 26;
}
}
Python
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False
s1Count, s2Count = [0] * 26, [0] * 26
for i in range(len(s1)):
s1Count[ord(s1[i]) - ord('a')] += 1
s2Count[ord(s2[i]) - ord('a')] += 1
matches = 0
for i in range(26):
matches += (1 if s1Count[i] == s2Count[i] else 0)
l = 0
for r in range(len(s1), len(s2)):
if matches == 26:
return True
index = ord(s2[r]) - ord('a')
s2Count[index] += 1
if s1Count[index] == s2Count[index]:
matches += 1
elif s1Count[index] + 1 == s2Count[index]:
matches -= 1
index = ord(s2[l]) - ord('a')
s2Count[index] -= 1
if s1Count[index] == s2Count[index]:
matches += 1
elif s1Count[index] - 1 == s2Count[index]:
matches -= 1
l += 1
return matches == 26
JavaScript
class Solution {
/**
* @param {string} s1
* @param {string} s2
* @return {boolean}
*/
checkInclusion(s1, s2) {
if (s1.length > s2.length) {
return false;
}
let s1Count = new Array(26).fill(0);
let s2Count = new Array(26).fill(0);
for (let i = 0; i < s1.length; i++) {
s1Count[s1.charCodeAt(i) - 97]++;
s2Count[s2.charCodeAt(i) - 97]++;
}
let matches = 0;
for (let i = 0; i < 26; i++) {
if (s1Count[i] === s2Count[i]) {
matches++;
}
}
let l = 0;
for (let r = s1.length; r < s2.length; r++) {
if (matches === 26) {
return true;
}
let index = s2.charCodeAt(r) - 97;
s2Count[index]++;
if (s1Count[index] === s2Count[index]) {
matches++;
} else if (s1Count[index] + 1 === s2Count[index]) {
matches--;
}
index = s2.charCodeAt(l) - 97;
s2Count[index]--;
if (s1Count[index] === s2Count[index]) {
matches++;
} else if (s1Count[index] - 1 === s2Count[index]) {
matches--;
}
l++;
}
return matches === 26;
}
}
