Solution For Permutation In String
Problem Statement:
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
Solution:
To solve this problem, we need to check whether the given substring s2 contains a permutation of s1. A permutation of s1 can be of any length, so we will use a sliding window approach to compare all the substrings of s2.
The basic idea of the sliding window approach is to maintain a window of size n (length of string s1) and slide it through the string s2. We will check at each iteration if the current window contains a valid permutation of s1. To achieve this, we will use a frequency map to count the occurrences of characters in s1 and s2.
We will create a hash array of size 26 to store the character count of s2. This hash array will represent the frequency map of s2. We will then slide the window of length s1.length() through the string s2 and check the frequency of characters in the current window. If the frequency of characters in the current window is same as that of the frequency map of s1, then it is a valid permutation of s1.
If we find a valid permutation in any of the substrings of s2, we will return true. Otherwise, we return false.
Algorithm:
- Create a hash array of size 26 to store the character count of s2.
- Fill the hash array with the character count of s1.
- Traverse through the string s2 using a sliding window approach.
- For each window of size s1.length(), check the frequency count of characters and compare it with the hash array.
- If the frequency count of characters in the current window matches the hash array, return true.
- If we reach the end of s2 without finding a valid permutation, return false.
Pseudocode:
int s1Length = s1.length();
int s2Length = s2.length();
int[] hashArray = new int[26];
// Fill hash array with count of each character in s1
for (int i=0; i<s1Length; i++) {
hashArray[s1.charAt(i)-‘a’]++;
}
int left = 0, right = 0;
// Traverse through s2 using sliding window approach
while (right<s2Length) {
// Slide window to right by 1 character
hashArray[s2.charAt(right)-‘a’]–;
// If window size exceeds s1.length(), slide window to left by 1 character
if (right-left+1 > s1Length) {
hashArray[s2.charAt(left)-‘a’]++;
left++;
}
// If current window contains valid permutation, return true
if (right-left+1 == s1Length && Arrays.equals(hashArray, new int[26])) {
return true;
}
// Move the right pointer to the next character
right++;
}
// If no valid permutation found, return false
return false;
Time Complexity:
The time complexity of this algorithm is O(s2.length()) where s2 is the length of the second string. We traverse through the string s2 only once and perform a constant time operation for each character.
Space Complexity:
The space complexity of this algorithm is O(1) as we are using a constant size hash array of 26. The space taken by other variables is also constant. Hence, the overall space complexity is O(1).
Conclusion:
In this problem, we have learned how to use a sliding window approach to check whether a given substring contains a permutation of another string. By using a frequency map, we can count the occurrences of characters in each string and compare them to find a valid permutation.
Step by Step Implementation For Permutation In String
public class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1 == null || s2 == null || s1.length() > s2.length()) {
return false;
}
int[] counts = new int[26];
for (int i = 0; i < s1.length(); i++) {
counts[s1.charAt(i) - 'a']++;
counts[s2.charAt(i) - 'a']--;
}
if (allZero(counts)) {
return true;
}
for (int i = s1.length(); i < s2.length(); i++) {
counts[s2.charAt(i) - 'a']--;
counts[s2.charAt(i - s1.length()) - 'a']++;
if (allZero(counts)) {
return true;
}
}
return false;
}
private boolean allZero(int[] counts) {
for (int i = 0; i < 26; i++) {
if (counts[i] != 0) {
return false;
}
}
return true;
}
}class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
# Base case
if len(s1) > len(s2):
return False
# Create a hashmap to store counts of characters in s1
s1_map = {}
for char in s1:
if char in s1_map:
s1_map[char] += 1
else:
s1_map[char] = 1
# Initialize counts of characters in the current window
window_map = {}
for i in range(len(s1)):
char = s2[i]
if char in window_map:
window_map[char] += 1
else:
window_map[char] = 1
# Check if the counts in the current window match those in s1_map
if self.check_maps_equal(s1_map, window_map):
return True
# Iterate through the remaining characters in s2, updating the counts
# in the current window as we go
for i in range(len(s1), len(s2)):
# Remove the leftmost character from the window
left_char = s2[i - len(s1)]
if window_map[left_char] == 1:
del window_map[left_char]
else:
window_map[left_char] -= 1
# Add the rightmost character to the window
right_char = s2[i]
if right_char in window_map:
window_map[right_char] += 1
else:
window_map[right_char] = 1
# Check if the counts in the current window match those in s1_map
if self.check_maps_equal(s1_map, window_map):
return True
# If we reach this point, it means that no permutation of s1 was found in s2
return False
def check_maps_equal(self, map1, map2):
# Check that map1 and map2 have the same keys
if set(map1.keys()) != set(map2.keys()):
return False
# Check that the values associated with each key are equal
for key in map1:
if map1[key] != map2[key]:
return False
# If we reach this point, it means that map1 and map2 are equal
return True// 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
// Note:
// The input strings only contain lower case letters.
// The length of both given strings is in range [1, 10,000].
/**
* @param {string} s1
* @param {string} s2
* @return {boolean}
*/
var checkInclusion = function(s1, s2) {
// create a hashmap to store the count of each character in s1
const map = {};
for (let i = 0; i < s1.length; i++) {
if (!map[s1[i]]) {
map[s1[i]] = 1;
} else {
map[s1[i]]++;
}
}
// create a left and right pointer
let left = 0;
let right = 0;
let count = s1.length;
// while the right pointer is less than the length of s2
while (right < s2.length) {
// if the character at the right pointer exists in the hashmap,
// decrease the count of that character by 1
if (map[s2[right]] !== undefined) {
map[s2[right]]--;
// if the character is equal to 0, meaning we found all occurrences of that character,
// decrease the total count by 1
if (map[s2[right]] === 0) {
count--;
}
}
right++;
// if the count is equal to 0, meaning we found all the characters in s1 in s2
if (count === 0) {
return true;
}
// if the right pointer - left pointer is equal to the length of s1, meaning we reached the end of the window
// we need to move the left pointer to the right by 1 to keep the window the same size
if (right - left === s1.length) {
// if the character at the left pointer exists in the hashmap,
// increase the count of that character by 1
if (map[s2[left]] !== undefined) {
map[s2[left]]++;
// if the character is equal to 1, meaning we need to find one more occurrence of that character,
// increase the total count by 1
if (map[s2[left]] === 1) {
count++;
}
}
left++;
}
}
// if we reach the end of the loop and the count is not 0,
// it means we were not able to find all the characters from s1 in s2
return count === 0;
};class Solution {
public:
bool checkInclusion(string s1, string s2) {
int len1 = s1.size(), len2 = s2.size();
if (len1 > len2) return false;
vector cnt(26);
for (int i = 0; i < len1; ++i) {
++cnt[s1[i] - 'a'];
--cnt[s2[i] - 'a'];
}
if (all_of(cnt.begin(), cnt.end(), [](int x) { return x == 0; })) return true;
for (int i = len1; i < len2; ++i) {
if (all_of(cnt.begin(), cnt.end(), [](int x) { return x == 0; })) return true;
--cnt[s2[i] - 'a'];
++cnt[s2[i - len1] - 'a'];
}
return all_of(cnt.begin(), cnt.end(), [](int x) { return x == 0; });
}
}; public class Solution {
public bool CheckInclusion(string s1, string s2) {
// base case
if (s1.Length > s2.Length) return false;
// create a hashmap to keep track of the characters in s1
var map = new Dictionary();
foreach (var c in s1) {
if (!map.ContainsKey(c)) {
map.Add(c, 1);
} else {
map[c]++;
}
}
// two pointers - left and right
var left = 0;
var right = 0;
var count = s1.Length;
// loop through s2
while (right < s2.Length) {
// if the character at the right pointer is in the hashmap,
// decrease the count of that character
if (map.ContainsKey(s2[right])) {
map[s2[right]]--;
// if the character count becomes 0, that means we have found
// all the characters in s1 in s2
if (map[s2[right]] == 0) {
count--;
}
}
right++;
// if count == 0, that means we have found all the characters in s1 in s2
if (count == 0) return true;
// if the current window size is greater than the size of s1,
// we need to remove the leftmost character from the current window
if (right - left == s1.Length) {
// if the character at the left pointer is in the hashmap,
// we need to increase the count of that character
if (map.ContainsKey(s2[left])) {
map[s2[left]]++;
// if the character count is greater than 0, that means we need to
// include that character in the current window
if (map[s2[left]] > 0) {
count++;
}
}
left++;
}
}
return false;
}
}