In Permutation in String, we are given two strings s1 and s2, and we need to check whether any permutation of s1 exists as a substring inside s2.
A permutation means the same characters are arranged in any order. So, instead of generating all possible arrangements of s1, we only need to check whether any substring of s2 has the same character frequency as s1.
Example 1
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: The substring "ba" exists inside s2, and "ba" is a permutation of "ab".
Example 2
Input: s1 = "ab", s2 = "eidboaoo"
Output: false
Explanation: No substring of s2 has the same character frequency as s1.
Example 3
Input: s1 = "adc", s2 = "dcda"
Output: true
Explanation: The substring "dca" exists inside s2, and it is a permutation of "adc".
Brute Force Approach
A permutation of s1 must have the same length and the same characters as s1. Therefore, only length-m windows of s2 need to be checked.
Sorting both strings gives the same ordered form when their characters match, so each candidate window can be sorted and compared with a pre-sorted copy of s1.
Algorithm
The lengths of s1 and s2 are stored in m and n. A valid permutation must have exactly m characters, so if m is greater than n, false is returned because s1 cannot appear inside a shorter string s2.
A sorted copy of s1 is created. This sorted string is used as the reference because every permutation of s1 becomes the same string after sorting.
The starting index start is moved from 0 to n - m. These are all possible starting positions of substrings in s2 having length m.
For every start index, a substring of length m is taken from s2. This substring starts at start and ends at start + m - 1.
The current substring is sorted and compared with the sorted version of s1. If both sorted strings are equal, true is returned because the current substring contains exactly the same characters as s1.
If all windows of length m are checked and no sorted window matches the sorted s1, false is returned.
Dry Run
Permutation in String Brute Force Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Checks every length-m window after sorting its characters. bool checkInclusion(string s1, string s2) { int m = s1.size(); int n = s2.size(); // No window in s2 can match when s1 is longer. if (m > n) { return false; } string sortedS1 = s1; sort(sortedS1.begin(), sortedS1.end()); // Check every possible window having the same length as s1. for (int start = 0; start <= n - m; start++) { string window = s2.substr(start, m); sort(window.begin(), window.end()); // Equal sorted forms mean the window is a permutation of s1. if (window == sortedS1) { return true; } } return false; }};int main() { string s1 = "ab"; string s2 = "eidbaooo"; Solution solution; cout << (solution.checkInclusion(s1, s2) ? "true" : "false") << endl; return 0;}Complexity Analysis
Time Complexity: O(N * M log M), where N is the length of s2 and M is the length of s1. There can be around N windows of length M, and sorting each window takes O(M log M) time.
Space Complexity: O(M), because each window substring of length M may be copied and sorted.
Better Approach
Sorting is unnecessary because two strings are permutations exactly when their character frequencies match.
Build the frequency pattern of s1 once, then create and compare a fresh frequency array for every length-m window of s2. This removes sorting, though overlapping windows are still recounted.
Algorithm
The lengths of s1 and s2 are stored in m and n. If m is greater than n, false is returned because no window of s2 can have enough characters to match s1.
A frequency array s1Freq of size 26 is created. It stores how many times each lowercase character appears in s1.
The starting index start is moved from 0 to n - m because only windows of length m can be valid candidates.
For every start index, a fresh frequency array windowFreq is created. This array stores the character frequencies of the current window in s2 from start to start + m - 1.
The current window is traversed, and every character frequency is added to windowFreq.
After building the frequency of the current window, windowFreq is compared with s1Freq. If both arrays are equal, true is returned because the current window is a permutation of s1.
If no window has the same frequency as s1, false is returned.
Dry Run
Permutation in String Better Approach Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Checks each window using character-frequency comparison. bool checkInclusion(string s1, string s2) { int m = s1.size(); int n = s2.size(); // No window in s2 can match when s1 is longer. if (m > n) { return false; } vector<int> s1Freq(26, 0); // Store the required frequency pattern of s1. for (char ch : s1) { s1Freq[ch - 'a']++; } // Rebuild the frequency array for every candidate window. for (int start = 0; start <= n - m; start++) { vector<int> windowFreq(26, 0); // Count characters inside the current length-m window. for (int i = start; i < start + m; i++) { windowFreq[s2[i] - 'a']++; } // Matching frequencies confirm a permutation. if (windowFreq == s1Freq) { return true; } } return false; }};int main() { string s1 = "ab"; string s2 = "eidbaooo"; Solution solution; cout << (solution.checkInclusion(s1, s2) ? "true" : "false") << endl; return 0;}Complexity Analysis
Time Complexity: O(N * M), where N is the length of s2 and M is the length of s1. For every possible window, the frequency array is rebuilt by traversing M characters. Comparing two arrays of size 26 takes constant time.
Space Complexity: O(1), because the frequency arrays have fixed size 26.
Optimal Approach
Adjacent length-m windows overlap in all but two positions, so rebuilding their frequencies wastes work.
Keep one frequency array for the active window. When it slides right, add the incoming character and remove the outgoing character. If this updated frequency array ever matches s1Freq, a permutation has been found.
Algorithm
The lengths of s1 and s2 are stored in m and n. If m is greater than n, false is returned because no substring of s2 can have enough characters to match s1.
Two frequency arrays of size 26 are created. The array s1Freq stores the required character frequencies from s1, and windowFreq stores the character frequencies of the current window in s2.
The first window of length m is built from s2. At the same time, s1Freq is filled using s1.
After this setup, s1Freq represents the required frequency pattern, and windowFreq represents the first candidate window in s2.
If the first window frequency matches s1Freq, true is returned immediately because a permutation has been found at the beginning of s2.
The window is then moved by taking right from m to n - 1. For every right index, s2[right] is added to windowFreq because it enters the window.
The character s2[right - m] is removed from windowFreq because it leaves the window from the left. This keeps the window size exactly equal to m.
After every slide, windowFreq is compared with s1Freq. If both arrays are equal, true is returned. If all windows are checked and no match is found, false is returned.
Dry Run
Permutation in String Optimal Approach Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Checks whether s2 contains // any permutation of s1. bool checkInclusion(string s1, string s2) { int m = s1.size(); int n = s2.size(); // No valid window can exist // when s1 is longer than s2. if (m > n) { return false; } vector<int> s1Freq(26, 0); vector<int> windowFreq(26, 0); // Build frequencies for s1 // and the first window of s2. for (int i = 0; i < m; i++) { s1Freq[s1[i] - 'a']++; windowFreq[s2[i] - 'a']++; } // The first window may // already be a permutation. if (s1Freq == windowFreq) { return true; } // Slide the fixed-size window // across the remaining string. for (int right = m; right < n; right++) { windowFreq[s2[right] - 'a']++; int outgoingIndex = right - m; windowFreq[s2[outgoingIndex] - 'a']--; // Matching frequencies confirm // a permutation inside s2. if (s1Freq == windowFreq) { return true; } } return false; }};int main() { string s1 = "ab"; string s2 = "eidbaooo"; Solution solution; cout << ( solution.checkInclusion(s1, s2) ? "true" : "false" ) << endl; return 0;}Complexity Analysis
Time Complexity: O(N + M), where N is the length of s2 and M is the length of s1. The first window and s1 are processed once, and then the fixed-size window slides through s2. Frequency comparison takes constant time because the array size is fixed at 26.
Space Complexity: O(1), because only two fixed-size frequency arrays of size 26 are used.
FAQs
Q1. Why is only a window of length s1 checked?
Any permutation of s1 must have exactly the same length as s1. Therefore, only substrings of s2 with that length can be valid.
Q2. Why are character frequencies used?
Two strings are permutations of each other only when every character appears the same number of times in both strings.
Q3. Why is the frequency-count approach better than sorting?
Frequency counting avoids sorting every window. Instead of arranging characters, it directly compares how many times each character appears.
Q4. What happens if s1 is longer than s2?
No substring of s2 can have enough characters to match s1, so false is returned.
Q5. Is it necessary to generate all permutations of s1?
No. Generating all permutations is unnecessary and inefficient. Frequency matching is enough to confirm whether two strings are permutations.
Be the first to add a comment.