Check if Permutation of Pattern is Substring
Last Updated :
16 Jan, 2025
Given two strings txt and pat having lowercase letters, the task is to check if any permutation of pat is a substring of txt.
Examples:
Input: txt = "geeks", pat = "eke"
Output: true
Explanation: "eek" is a permutation of "eke" which exists in "geeks".
Input: txt = "programming", pat = "rain"
Output: false
Explanation: No permutation of "rain" exists as a substring in "programming".
[Naive Approach] Checking all possible substrings
The idea is to iterate over all possible substrings of txt having the same length as pat. For each substring of txt, check if pat is a permutation of the substring. Two strings are said to be permutations of each other if they contain the same characters with the same frequencies, but possibly in a different order. So, we can match the frequency of each character in both the strings to check if they are permutations of each other or not.
C++
// C++ Program to check if any permutation of pattern
// is substring by checking all possible substrings
#include <iostream>
#include <vector>
using namespace std;
const int MAX_CHAR = 26;
bool arePermutations(string &txt, int startIdx, string &pat) {
vector<int> freq(MAX_CHAR, 0);
for (int i = 0; i < pat.length(); i++) {
// Decrement the count of character in txt
freq[txt[startIdx + i] - 'a'] -= 1;
// Increment the count of character in pat
freq[pat[i] - 'a'] += 1;
}
for (int i = 0; i < MAX_CHAR; i++) {
if (freq[i] != 0)
return false;
}
return true;
}
bool search(string &txt, string &pat) {
int n = txt.length();
int m = pat.length();
for (int i = 0; i < n - m + 1; i++) {
// Check if substring in txt starting from i
// is a permutation of pat
if (arePermutations(txt, i, pat))
return true;
}
return false;
}
int main() {
string txt = "geeks";
string pat = "eke";
if (search(txt, pat))
cout << "true";
else
cout << "false";
return 0;
}
// C Program to check if any permutation of pattern
// is substring by checking all possible substrings
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define MAX_CHAR 26
bool arePermutations(char *txt, int startIdx, char *pat) {
int freq[MAX_CHAR] = {0};
int i;
for (i = 0; i < strlen(pat); i++) {
// Increment the count of character in txt
freq[txt[startIdx + i] - 'a'] += 1;
// Decrement the count of character in pat
freq[pat[i] - 'a'] -= 1;
}
for (i = 0; i < MAX_CHAR; i++) {
if (freq[i] != 0)
return false;
}
return true;
}
int search(char *txt, char *pat) {
int n = strlen(txt);
int m = strlen(pat);
int i;
for (i = 0; i < n - m + 1; i++) {
// Check if substring in txt starting from i
// is a permutation of pat
if (arePermutations(txt, i, pat))
return true;
}
return false;
}
int main() {
char txt[] = "geeks";
char pat[] = "eke";
if (search(txt, pat))
printf("true\n");
else
printf("false\n");
return 0;
}
// Java Program to check if any permutation of pattern
// is substring by checking all possible substrings
class GfG {
static final int MAX_CHAR = 26;
static boolean arePermutations(String txt, int startIdx, String pat) {
int[] freq = new int[MAX_CHAR];
for (int i = 0; i < pat.length(); i++) {
// Increment the count of character in txt
freq[txt.charAt(startIdx + i) - 'a'] += 1;
// Decrement the count of character in pat
freq[pat.charAt(i) - 'a'] -= 1;
}
for (int i = 0; i < MAX_CHAR; i++) {
if (freq[i] != 0)
return false;
}
return true;
}
static boolean search(String txt, String pat) {
int n = txt.length();
int m = pat.length();
for (int i = 0; i < n - m + 1; i++) {
// Check if substring in txt starting from i
// is a permutation of pat
if (arePermutations(txt, i, pat))
return true;
}
return false;
}
public static void main(String[] args) {
String txt = "geeks";
String pat = "eke";
if (search(txt, pat))
System.out.println("true");
else
System.out.println("false");
}
}
# Python Program to check if any permutation of pattern
# is substring by checking all possible substrings
MAX_CHAR = 26
def arePermutations(txt, startIdx, pat):
freq = [0] * MAX_CHAR
for i in range(len(pat)):
# Increment the count of character in txt
freq[ord(txt[startIdx + i]) - ord('a')] += 1
# Decrement the count of character in pat
freq[ord(pat[i]) - ord('a')] -= 1
for i in range(MAX_CHAR):
if freq[i] != 0:
return False
return True
def search(txt, pat):
n = len(txt)
m = len(pat)
for i in range(n - m + 1):
# Check if substring in txt starting from i
# is a permutation of pat
if arePermutations(txt, i, pat):
return True
return False
if __name__ == "__main__":
txt = "geeks"
pat = "eke"
if search(txt, pat):
print("true")
else:
print("false")
// C# Program to check if any permutation of pattern
// is substring by checking all possible substrings
using System;
class GfG {
const int MAX_CHAR = 26;
static bool arePermutations(string txt, int startIdx, string pat) {
int[] freq = new int[MAX_CHAR];
for (int i = 0; i < pat.Length; i++) {
// Increment the count of character in txt
freq[txt[startIdx + i] - 'a'] += 1;
// Decrement the count of character in pat
freq[pat[i] - 'a'] -= 1;
}
for (int i = 0; i < MAX_CHAR; i++) {
if (freq[i] != 0)
return false;
}
return true;
}
static bool search(string txt, string pat) {
int n = txt.Length;
int m = pat.Length;
for (int i = 0; i < n - m + 1; i++) {
// Check if substring in txt starting from i
// is a permutation of pat
if (arePermutations(txt, i, pat))
return true;
}
return false;
}
static void Main() {
string txt = "geeks";
string pat = "eke";
if (search(txt, pat))
Console.WriteLine("true");
else
Console.WriteLine("false");
}
}
// JavaScript Program to check if any permutation of pattern
// is substring by checking all possible substrings
const MAX_CHAR = 26;
function arePermutations(txt, startIdx, pat) {
let freq = new Array(MAX_CHAR).fill(0);
for (let i = 0; i < pat.length; i++) {
// Increment the count of character in txt
freq[txt.charCodeAt(startIdx + i) - 'a'.charCodeAt(0)] += 1;
// Decrement the count of character in pat
freq[pat.charCodeAt(i) - 'a'.charCodeAt(0)] -= 1;
}
for (let i = 0; i < MAX_CHAR; i++) {
if (freq[i] !== 0)
return false;
}
return true;
}
function search(txt, pat) {
let n = txt.length;
let m = pat.length;
for (let i = 0; i < n - m + 1; i++) {
// Check if substring in txt starting from i
// is a permutation of pat
if (arePermutations(txt, i, pat))
return true;
}
return false;
}
// Driver Code
let txt = "geeks";
let pat = "eke";
if (search(txt, pat))
console.log("true");
else
console.log("false");
Time Complexity: O(n*m), where n is the length of txt and m is the length of pat.
Auxiliary Space: O(MAX_CHAR), where MAX_CHAR = 26 as txt and pat have lowercase letters only.
[Expected Approach] Using Sliding Window
The idea is similar to the previous approach where we check if pat is a permutation of any substring of txt but instead of comparing each substring from the beginning, we can use Sliding Window Technique and slide a window of the same size as pat. When a new character is added to the window, we increase its frequency by 1 and when a character is removed from the window, we decrease its frequency by 1.
C++
// C++ Program to check if any permutation of string
// is substring using Sliding Window Technique
#include <iostream>
#include <vector>
using namespace std;
const int MAX_CHAR = 26;
// check if all characters have 0 frequency
bool check(vector<int> &freq) {
for(int i = 0; i < MAX_CHAR; i++) {
if(freq[i] != 0)
return false;
}
return true;
}
bool search(string &txt, string &pat) {
int n = txt.length();
int m = pat.length();
vector<int> freq(MAX_CHAR, 0);
// construct the first window
for(int i = 0; i < m; i++) {
freq[txt[i] - 'a'] += 1;
freq[pat[i] - 'a'] -= 1;
}
// Check for first window
if(check(freq))
return true;
for (int i = m; i < n; i++) {
// Add the ith character into the window
freq[txt[i] - 'a'] += 1;
// Remove the (i - m)th character from the window
freq[txt[i - m] - 'a'] -= 1;
// Check for the current window
if (check(freq))
return true;
}
return false;
}
int main() {
string txt = "geeks";
string pat = "eke";
if (search(txt, pat))
cout << "true";
else
cout << "false";
return 0;
}
// C Program to check if any permutation of string
// is substring using Sliding Window Technique
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define MAX_CHAR 26
// check if all characters have 0 frequency
bool check(int freq[]) {
for (int i = 0; i < MAX_CHAR; i++) {
if (freq[i] != 0)
return false;
}
return true;
}
bool search(char *txt, char *pat) {
int n = strlen(txt);
int m = strlen(pat);
// construct the first window
int freq[MAX_CHAR] = {0};
for (int i = 0; i < m; i++) {
freq[txt[i] - 'a'] += 1;
freq[pat[i] - 'a'] -= 1;
}
// Check for first window
if (check(freq))
return true;
for (int i = m; i < n; i++) {
// Add the ith character into the window
freq[txt[i] - 'a'] += 1;
// Remove the (i - m)th character from the window
freq[txt[i - m] - 'a'] -= 1;
// Check for the current window
if (check(freq))
return true;
}
return false;
}
int main() {
char txt[] = "geeks";
char pat[] = "eke";
if (search(txt, pat))
printf("true");
else
printf("false");
return 0;
}
// Java Program to check if any permutation of string
// is substring using Sliding Window Technique
import java.util.*;
class GfG {
static final int MAX_CHAR = 26;
// check if all characters have 0 frequency
static boolean check(int[] freq) {
for (int i = 0; i < MAX_CHAR; i++) {
if (freq[i] != 0)
return false;
}
return true;
}
static boolean search(String txt, String pat) {
int n = txt.length();
int m = pat.length();
// construct the first window
int[] freq = new int[MAX_CHAR];
Arrays.fill(freq, 0);
for (int i = 0; i < m; i++) {
freq[txt.charAt(i) - 'a'] += 1;
freq[pat.charAt(i) - 'a'] -= 1;
}
// Check for first window
if (check(freq))
return true;
for (int i = m; i < n; i++) {
// Add the ith character into the window
freq[txt.charAt(i) - 'a'] += 1;
// Remove the (i - m)th character from the window
freq[txt.charAt(i - m) - 'a'] -= 1;
// Check for the current window
if (check(freq))
return true;
}
return false;
}
public static void main(String[] args) {
String txt = "geeks";
String pat = "eke";
if (search(txt, pat))
System.out.println("true");
else
System.out.println("false");
}
}
# Python Program to check if any permutation of string
# is substring using Sliding Window Technique
MAX_CHAR = 26
# check if all characters have 0 frequency
def check(freq):
for i in range(MAX_CHAR):
if freq[i] != 0:
return False
return True
def search(txt, pat):
n = len(txt)
m = len(pat)
# construct the first window
freq = [0] * MAX_CHAR
for i in range(m):
freq[ord(txt[i]) - ord('a')] += 1
freq[ord(pat[i]) - ord('a')] -= 1
# Check for first window
if check(freq):
return True
for i in range(m, n):
# Add the ith character into the window
freq[ord(txt[i]) - ord('a')] += 1
# Remove the (i - m)th character from the window
freq[ord(txt[i - m]) - ord('a')] -= 1
# Check for the current window
if check(freq):
return True
return False
if __name__ == "__main__":
txt = "geeks"
pat = "eke"
if search(txt, pat):
print("true")
else:
print("false")
// C# Program to check if any permutation of string
// is substring using Sliding Window Technique
using System;
class GfG {
const int MAX_CHAR = 26;
// check if all characters have 0 frequency
static bool check(int[] freq) {
for (int i = 0; i < MAX_CHAR; i++) {
if (freq[i] != 0)
return false;
}
return true;
}
static bool search(string txt, string pat) {
int n = txt.Length;
int m = pat.Length;
// construct the first window
int[] freq = new int[MAX_CHAR];
for (int i = 0; i < m; i++) {
freq[txt[i] - 'a'] += 1;
freq[pat[i] - 'a'] -= 1;
}
// Check for first window
if (check(freq))
return true;
for (int i = m; i < n; i++) {
// Add the ith character into the window
freq[txt[i] - 'a'] += 1;
// Remove the (i - m)th character from the window
freq[txt[i - m] - 'a'] -= 1;
// Check for the current window
if (check(freq))
return true;
}
return false;
}
static void Main() {
string txt = "geeks";
string pat = "eke";
if (search(txt, pat))
Console.WriteLine("true");
else
Console.WriteLine("false");
}
}
// JavaScript Program to check if any permutation of string
// is substring using Sliding Window Technique
const MAX_CHAR = 26;
// check if all characters have 0 frequency
function check(freq) {
for (let i = 0; i < MAX_CHAR; i++) {
if (freq[i] !== 0)
return false;
}
return true;
}
function search(txt, pat) {
let n = txt.length;
let m = pat.length;
// construct the first window
let freq = new Array(MAX_CHAR).fill(0);
for (let i = 0; i < m; i++) {
freq[txt.charCodeAt(i) - 'a'.charCodeAt(0)] += 1;
freq[pat.charCodeAt(i) - 'a'.charCodeAt(0)] -= 1;
}
// Check for first window
if (check(freq))
return true;
for (let i = m; i < n; i++) {
// Add the ith character into the window
freq[txt.charCodeAt(i) - 'a'.charCodeAt(0)] += 1;
// Remove the (i - m)th character from the window
freq[txt.charCodeAt(i - m) - 'a'.charCodeAt(0)] -= 1;
// Check for the current window
if (check(freq))
return true;
}
return false;
}
// Driver Code
let txt = "geeks";
let pat = "eke";
if (search(txt, pat))
console.log("true");
else
console.log("false");
Time Complexity: O(n*MAX_CHAR), where n is the length of txt and MAX_CHAR = 26 as txt and pat have lowercase letters only.
Auxiliary Space: O(1)
Similar Reads
Check if two strings are permutation of each other
Write a function to check whether two given strings are Permutation of each other or not. A Permutation of a string is another string that contains same characters, only the order of characters can be different. For example, "abcd" and "dabc" are Permutation of each other. We strongly recommend that
14 min read
Check if a string is substring of another
Given two strings txt and pat, the task is to find if pat is a substring of txt. If yes, return the index of the first occurrence, else return -1. Examples : Input: txt = "geeksforgeeks", pat = "eks"Output: 2Explanation: String "eks" is present at index 2 and 9, so 2 is the smallest index. Input: tx
8 min read
Count of K-size substrings having palindromic permutations
Given string str consists of only lowercase alphabets and an integer K, the task is to count the number of substrings of size K such that any permutation of the substring is a palindrome. Examples: Input: str = "abbaca", K = 3 Output: 3 Explanation: The substrings of size 3 whose permutation is pali
9 min read
Check if permutation of one string can break permutation of another
Given two strings str1 and str2, the task is to check if any permutation of the given strings str1 and str2 is possible such that the character at each index of one string is greater than or equal to the other string. Examples: Input: A = "abc", B = "xya" Output: Yes Explanation: "ayx" is a permutat
6 min read
Check if any permutation of string is a K times repeated string
Given a string S and an integer K, the task is to check that if any permutation of the string can be formed by K times repeating any other string.Examples: Input: S = "abba", K = 2 Output: Yes Explanation: Permutations of given string - {"aabb", "abab", "abba", "baab", "baba", "bbaa"} As "abab" is r
13 min read
Check if one string is subsequence of other
Given two strings s1 and s2, find if the first string is a Subsequence of the second string, i.e. if s1 is a subsequence of s2. A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. Examples : Input: s1 =
10 min read
Permutations of given String
Given a string s, the task is to return all permutations of a given string in lexicographically sorted order. Note: A permutation is the rearrangement of all the elements of a string. Duplicate arrangement can exist. Examples: Input: s = "ABC"Output: "ABC", "ACB", "BAC", "BCA", "CAB", "CBA" Input: s
5 min read
Check if strings are rotations of each other or not | Set 2
Given two strings s1 and s2, check whether s2 is a rotation of s1. Examples: Input : ABACD, CDABA Output : True Input : GEEKS, EKSGE Output : True We have discussed an approach in earlier post which handles substring match as a pattern. In this post, we will be going to use KMP algorithm's lps (long
6 min read
Check if given String is Pangram or not
Given a string s, the task is to check if it is Pangram or not. A pangram is a sentence containing all letters of the English Alphabet. Examples: Input: s = "The quick brown fox jumps over the lazy dog" Output: trueExplanation: The input string contains all characters from ‘a’ to ‘z’. Input: s = "Th
6 min read
std::is_permutation in C++ STL
The C++ function std::algorithm::is_permutation() tests whether a sequence is permutation of other or not. It uses operator == for comparison. This function was defined in C++11. Syntax: template <class ForwardIterator1, class ForwardIterator2 >bool is_permutation(ForwardIterator1 first1, Forw
3 min read