Microsoft Interview Question
Software Engineer in TestsCountry: United States
Interview Type: Phone Interview
Yep. Create a set of letters from the smaller string (e.g. 'ab'). Advance character by character through the larger string, checking to see if current character is in the set. If it is, remove it from the set. If the set's empty, you're done. If not, keep advancing. If you find a character that's not in the set, advance to the next index, and repopulate the set from the smaller string.
showell30, I don't know if set would be the correct data structure. What if there were duplicate characters?
@Frank. If characters can repeat, you can maintain the difference in counts (between the window and the target string) and this idea would essentially work. Once a character count becomes zero, that means the window has the exact number required for that character (as we are maintaining difference). You can move it to a different set.
To check if a window matches, just check the length of the different set.
This is O(n) time (n is the length of the larger string).
@Loler and @showell
will this solution work if we are looking to find 'abc' within 'abac'
With this solution, when I hit the 2nd 'a' within 'abac' I would re-populate my set and advance to 'c'; which essentially tells me that the permutation of 'abc' is not present. Am I missing something obvious??
Given an input string A and the template string B, first use quicksort to sort B into B', and first |B| elements in A denoted as C; dynamically move C along A, each time the 1st element in C is removed and the next char is appended into C, just like insertion sort to sort C into C' and match C' == B'
Most practical solution.
This will take nlog(n) time. Don't know if it's even possible to do it faster.
Are we assuming that Input string A is always sorted? If not, this algorithm will not work.
It's Not O(n log n). It's O(n*m) because the window moves n steps, at EACH step we insert+compare (log m + m) >>> that is n*(log m+ m) = O(n*m)
lets say S1 is the main string and S2 is the substring why cant we do like this
S1= cdabfgd, S2=bac put s2 in character hash like hash[b]=1,hash[a]=1,hash[c]=1 and the length of s2 is 3 now iterate through s1 and check if the character exists in hash and decrement the corresponding hash value i.e when b is found in s1 make hash[b]-- lets maintain a global variable which increases it self when every time you decrease count in hash so when the global variable count becomes equal to length of s2 it means that the permutation of characters exist in s1.
I have an O(n) solution, please check the answer of mine below. I am using kmp search, more faster than you said.
Here is my thought: For the permutation of string, its simplified represents is the number of each character existed in the string. If you want to check if A's permutation is sub string of the B string, you only need to be sure that the number of each kind of character in A is less the number of the same character in the string B. So you can build a histogram of characters in A by going through A, then going through B, decrease the count of character histogram of A when it find the one in B. Return true when all histogram reach zero during the going through B, otherwise return false.
here is the code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int compare(const void *a,const void * b)
{
return (*(char*)a-*(char*)b);
}
int main()
{
char str[]="aabcdefgh";
char b[]="ba";
char c[10];
qsort(b,strlen(b),sizeof(char),compare);
int p=strlen(str);
int l=strlen(b);
int k,m;
for(int i=0;i<=p-l;i++)
{
m=0;
for(int j=i;j<i+l;j++)
{c[m++]=str[j];
}
qsort(c,l,sizeof(char),compare);
cout<<endl;
for(k=0;k<l;k++)
{ if(c[k]!=b[k]) break; }
if(k==l)
cout<<"string is found at location i= "<<i;
}
return 0;
}
- take each character in smaller string and add its position in larger string into sorted array
- if all chars are there in larger string, check if all the position is in sequence
Eg
String a = abcdefghij
String = dcfe
Sorted positions will be 3 4 5 6 so will return true
what if you have some chars occuring multiple times ?
example: string_1 = abcdeeffghijc
string_2 = dcfe
Also notice that by sorting the string, you disrupt the original order of chars in the string such that you have no way of telling for example if you are looking
for "cat" in "tsakc" or "cat" in "ckast"
Yes, this will work well only If string does not have repeating chars. Thanks for pointing it out
I am assuming it should return false for above case since lookalike question is a specific permutation of smaller string must be sub string of larger string
true but you are missing my point.
i think your algorithm would return false for "abcabcabc" and "cab" when it should return true;
public static bool isubstring(string S1, string S2)
{
int sumS1 = 0;
int sumS2 = 0;
for (int i = 0; i < S2.Length; i++)
{
sumS2 += (int)S2[i];
}
for (int i = 0; i < S1.Length - S2.Length + 1; i++)
{
int index = i;
sumS1 = 0;
for (int j = 0; j < S2.Length; j++)
{
sumS1 += (int)S1[index];
index++;
}
if (sumS1 == sumS2)
return true;
}
return false;
}
Few things
1) It is not correct. For instance, if adef is the long string and bc is the string sought, then you will say true, while it is clearly false. (Basically a+d = b+c)
Basically, sum being same does not imply you have gotten your string.
2) For long strings there is a good chance of overflows, and messing up your results even more, 1) not withstanding.
3) The runtime of this is O(|A||B|) where the string lengths are |A| and |B|.
(I should have stated, 2 and 3 are no biggies, but being incorrect is).
1- if long string = "adef" and "bc" is the string sought code return false not true
2- overflow is difficult to occur beacuse if the length of long string is 1000000000 and the length of sougth string is 1000000 the sum of the string = 122*1000000 in worst case
3- this method when we need to use O(1) space
for first case we need to check if sougth string contain one char of long string
if (sumS1 == sumS2 && S2.Contains(S1[index].ToString()))
return true;
get a element from string A, search for that in string B1(Copy of second string B),If we dont find it go to next element in A.
If we find element at position 'i' in B1, replace that element with 0 in B1(we did not modify anything in B).
search for the next element in A in B1 and replace that element with 0 in B1 till we could not find the a .elements of A in B1 or all elements in B1 are 0.
if all elements in B are 0.result is success.
if we could not find a element at position k of A in B1. get refresh B1 i.e copy from B.
now find for that element in B(the original string) if we could not find it in B, Continue to repeate the same steps from position k+1 .
if you find it in B,repeate steps from position i+1
To solve this problem.. First find the maximum window in which all the character of given pattern is present. If max window length is equal to pattern length than it is going to be the permutation of given string other wise not.Code is given below let me know if it fails in any scenario it is working for me for test cases i think of.
int FindpatLen(char *str,char *pat)
{
if(!*str)
return 0;
int len1=strlen(str),len2=strlen(pat),count=0;
int hasfound[26]={0},needtofound[26]={0};
int i=0,begin=0,max=999;
for(i=0;i<len2;i++)
needtofound[pat[i]-97]++;
i=0;
for(;i<len1;i++)
{
if(needtofound[str[i]-97]==0)
continue;
hasfound[str[i]-97]++;
if(hasfound[str[i]-97]<=needtofound[str[i]-97])
count++;
if(count==len2)
{
while((needtofound[str[begin]-97]==0) || (hasfound[str[begin]-97]>needtofound[str[begin]-97]))
{
if(hasfound[str[begin]-97]>needtofound[str[begin]-97])
hasfound[str[begin]-97]--;
begin++;
}
if(max>(i-begin))
max=i-begin+1;
}
}
return max;
}
bool Ispermutation(char *str,char *pat)
{
int len=strlen(pat);
if(len==FindpatLen(str,pat))
return true;
return false;
}
int main()
{
char str[]="abcabcabc";
char pat[]="cab";
bool res=Ispermutation(str,pat);
getchar();
return 0;
}
1.Create a temporary bitMap of <character,Bit> initialize them with character and bit value 0
2. Scan through the big array when you find a character in the small array update the bit map with the char and set it to 1 if the character bit has 0.
public static boolean checkPresence(char[] arr, char[] temp) {
int track = 0;
Map<Character, Integer> tempMap = new HashMap<Character, Integer>();
for (char c : temp) {
tempMap.put(c, 0);
}
int prev = 0;
for (int i = 0; i < arr.length; i++) {
char c = arr[i];
if (tempMap.get(c) != null && tempMap.get(c) == 0
&& (prev == 0 || prev == i - 1)) {
tempMap.put(c, 1);
track++;
prev = i;
}
}
return track == temp.length ? true : false;
}
Let me know if i miss any case
package com.santosh.career;
import java.util.HashMap;
import java.util.Map;
public class Career15555796 {
/**
* @param args
*/
public static void main(String[] args) {
char[] small = { 'c', 'b' };
char[] big = { 'g', 'b', 'a', 'c', 'd', 'e' };
Map<Character, Integer> charMap = new HashMap<Character, Integer>(26);
Map<Character, Integer> fixedCharMap = new HashMap<Character, Integer>(
26);
resetCharMap(small, charMap);
resetCharMap(small, fixedCharMap);
int smallCount = small.length;
int flag = 0;
for (char c : big) {
if (charMap.get(c) != null) {
charMap.put(c, charMap.get(c) - 1);
flag = 1;
smallCount--;
}
if(smallCount==0){
System.out.println("Found a match");
break;
}
if (flag == 1 && charMap.get(c) == null) {
charMap = fixedCharMap;
flag = 0;
smallCount = small.length;
}
}
}
private static void resetCharMap(char[] small,
Map<Character, Integer> charMap) {
for (char c : small) {
if (charMap.get(c) == null) {
charMap.put(c, 1);
} else {
charMap.put(c, charMap.get(c));
}
}
}
}
package questions;
import java.util.Arrays;
public class HasPerm {
public static void main(String[] args) {
System.out.println(hasPerm("abcdefg", "ba"));
System.out.println(hasPerm("abcdefg", "gf"));
System.out.println(hasPerm("abcdefg", "dc"));
}
public static boolean hasPerm(String source, String find) {
String k = key(find);
for (int i = 0; (i + find.length()) <= source.length(); ++i) {
String sub = source.substring(i, i + find.length());
if (key(sub).equals(k))
return true;
}
return false;
}
private static String key(String s) {
char[] ary = s.toCharArray();
Arrays.sort(ary);
return new String(ary);
}
}
How about this, you just sort both the strings and then compare the index of the smaller string in the larger string. If it is -1, then the smaller string is not a part of the larger string.
import java.util.*;
public class sort {
public static void main(String args[])
{
String str1 = "abcdefgh";
String str2 = "fed";
char a[] = str1.toCharArray();
Arrays.sort(a);
String new_str_1 = new String(a);
System.out.println(new_str_1);
char b[] = str2.toCharArray();
Arrays.sort(b);
String new_str_2 = new String(b);
System.out.println(new_str_2);
if(new_str_1.indexOf(new_str_2) != -1)
{
System.out.println("True");
}
else
{
System.out.println("False");
}
}
}
reverse the second string and use kmp search will be better. and also we can use suffix tree or suffix array, but they are too complicated. here is my program, and it will take O(n) time complexity(n: the length of first string) and O(m) space complexity(m: the length of second string):
#include<iostream>
#include<string>
using namespace std;
void swap(char *a, char *b) {
char temp;
temp = *a;
*a = *b;
*b = temp;
}
void reverse(char *p_start, char *p_end) {
while(p_start < p_end) {
swap(p_start, p_end);
p_start++;
p_end--;
}
}
void get_next(char *p, int len, int *next) {
int j = -1;
int i = 0;
next[i] = -1;
while(i < len - 1) {
if(j == -1 || p[i] == p[j]) {
++i;
++j;
if(p[i] != p[j])
next[i] = j;
else
next[i] = next[j];
} else {
j = next[j];
}
}
}
char *kmp_search(char *s, int s_len, char *p, int p_len) {
if(NULL == s || NULL == p || 0 == s_len || 0 == p_len)
return NULL;
int *next = (int*)malloc(sizeof(int) * p_len);
memset(next, 0, sizeof(int) * p_len);
get_next(p, p_len, next);
int i = 0;
int j = 0;
while(i < s_len && j < p_len) {
if(j == -1 || s[i] == p[j]) {
++i;
++j;
} else {
j = next[j];
}
}
if(next)
free(next);
if(j >= p_len)
return s + i - p_len;
else
return NULL;
}
int is_contain_permutation(char *s, char *d) {
if(NULL == s || NULL == d)
return 0;
int s_len = strlen(s);
int d_len = strlen(d);
char *temp = (char*)malloc(d_len + 1);
strcpy(temp, d);
reverse(temp, temp + d_len - 1);
char *ret = kmp_search(s, s_len, temp, d_len);
if(temp)
free(temp);
if(ret)
return 1;
else
return 0;
}
int main(int argc, char *argv[]) {
char s[] = "abcdefg";
char d[] = "ba";
is_contain_permutation(s, d);
cin.get();
return 0;
}
I think of hashing all the characters into the hashtable and maintain the count. Then, for every character in S2, check if it exists in the hashtable. if so, then result is true. it takes o(n) where n is the size of the longest string.
This idea is not based on the order and it depends whether there exists every character of a string exists in the original string. When it exists, the permutation is possible (obviously)
How about this:
p1 = &Array1;
strcpy(Array3, Array2);
while (*p1 != '\0')
{
for (i = (p1 - Array1); i < ((p1-Array1) + strlen(Array2)); i++)
{
for (j = 0; j < strlen(Array2); j++)
{
if (Array1[i] == Array2[j])
{
Array2[j] = 'x';
count++;
break;
}
}
}
if(count == strlen(Array2))
{
success = 1;
break;
}
else
{
p1++;
strcpy(Array2, Array3);
count = 0;
}
}
if (success == 1)
{
printf("Success");
}
else
{
printf("Failure");
}
Check if a substring permutation exists in a string
Check if a substring permutation exists in a string. Ex. A = “most random” B = “mod”
So the function should return true since “mod” a permutation of “dom” exists in string A
—————————————————————————————————————–
// Have this as class field to expose to multiple methods
private Hashtable mTable;public bool SubStringExistsAsPermutation(string A, string B)
{
if (String.IsNullOrEmpty(A))
{
throw new ArgumentException(“A cannot be null”);
}
if (String.IsNullOrEmpty(B))
{
throw new ArgumentException(“B cannot be null”);
}
mTable = new Hashtable();
// Fill hashtable with B string
foreach (char ch in B)
{
mTable[ch] = Convert.ToInt32(mTable[ch]) + 1;
}
// Read each character from String A. Keep comparing it with hashtable characters
// If character in A is not found in hashtable, keep moving A pointer
// If character in A is found in hashtable, Set a flag LookForConsecutiveCharacter = true
// If you find LookForConsecutiveCharacter = true, and next character is not found Then –
// Set LookForConsecutiveCharacter = false and reset hashmap to its initial state to look for next pattern ahead
bool LookForConsecutiveCharacter = false;
int count = 0;
foreach(char ch in A)
{
if (count == B.Length)
{
break;
}
if (Convert.ToInt32(mTable[ch]) >= 1)
{
mTable[ch] = Convert.ToInt32(mTable[ch]) – 1;
LookForConsecutiveCharacter = true;
count++;
}
else
{
// If we expected consecutive characters for permutation and its not found, reset hashtable
if (LookForConsecutiveCharacter)
{
ResetHashTableToDefault(B);
LookForConsecutiveCharacter = false;
count = 0;
}
}
}
// Verify if we found permutation
bool permutationFound = true;
foreach (char key in mTable.Keys)
{
if (Convert.ToInt32(mTable[key]) != 0)
{
permutationFound = true;
break;
}
}
return permutationFound;
}
private void ResetHashTableToDefault(string B)
{
mTable.Clear();
foreach (char key in B)
{
mTable[key] = Convert.ToInt32(mTable[key]) + 1;
}
}
bool find_permutation(const string& str, const string& other)
{
string sorted;
sort(other, sorted); //O(nlogn)
for(int i = 0; i < str.length(); ++i)
{
if(i + sorted.length() < str.length())
{
string subs = str.substr(i, sorted.length());
string sortedSub;
sort(subs, sortedSub); //O(klogk)
if(sortedSub == sorted) return true;
}
}
return false;
}
We can do this in O(n). The algorithm is simple, we move a window of |p| from left to right, and keep a counter of characters passed. We also update a counter d whenever a match
between the moving counter and histogram of p happens or otherwise.
def persub(s, p):
pc = Counter(p)
cc = Counter()
d = 0
for i, c in enumerate(s):
_cc = cc.get(c, 0)
if c in pc and _cc == pc[c]:
d -= 1
cc[c] = _cc + 1
if cc[c] == pc[c]:
d += 1
if i >= len(p):
_c = s[i - len(p)]
_cc = cc.get(_c, 0)
if _c in pc and _cc == pc[_c]:
d -= 1
cc[_c] = _cc - 1
if cc[_c] == pc[_c]:
d += 1
if d == len(pc):
yield i - len(p) + 1
Guys we need to find a substring of string 1 which consists of only characters of string2 and has same length as string 2, once while iterating you find such a substring then compare the count of each character in the substring and string 2 , if string 2 has all unique characters this
problem becomes simply finding the longest substring in string 1 that consists of all unique characters , characters here being those of string 2 , then if the length of this longest substring equals length of string 2 , then this is the code
i m posting the c code
#include<stdio.h>
#include<iostream>
using namespace std;
void printallpermutations(char* a , char* b)
{
int i;
bool aux[26]={0};
int visited[26]={-1};
int current_substring_begin=0;
int max_substring_len=0;
int max_substring_begin=0;
for(int i=0;b[i]!='\0';++i)aux[b[i]]=1;
while(a[current_substring_begin]!='\0')
{
while(b[a[i]]==0)i++;
count=0;
//first char encountered
current_substring_begin=i;
while(b[a[i]])
{
if(visited[a[i]]==-1){
visited[a[i]]=i;
count++;
}
else{
//it occurs but has previous occurence , if previous occurence is after current begin, then its a duplicate within current substring
//and the current unique substring ends one char before this char and the new begins after the previous visited val
if(visited[a[i]]>=current_substring_begin)
{
//substring ends
if(count>max_substring_len){
max_substring_len=count;
max_substring_begin=current_substring_begin;
current_substring_begin=visited[a[i]]+1;//start from next char since last visit
}
}
}
}
}
if(max_substring_len==strlen(b)){
cout<<"contains";
for(int p=max_substring_begin;p<max_substring_begin+max_substring_len;++p)cout<<a[p];
}
else cout<<"doesnot contains";
return;
}
int main()
{
char a[] = "abcdnmpbacdmnpccc";
char b[] = "pmn";
printallpermutations(a,b);
return 0;
}
Please check out this generic solution, that will work on all cases, even if the text is not sorted.
we create all possible permutations of a pattern and then simply compare.
class P13
{
static String text;
static boolean result = false;
public static void main(String[] args)
{
text = "badfcge";
String patt = "fcd";
permutations(patt);
System.out.println(result);
}
public static void permutations(String patt)
{
permutations("",patt);
}
public static void permutations(String prefix, String patt)
{
int l = patt.length();
if(l == 0)
{
//System.out.println(prefix);
if(search(text, prefix))
result = true;
}
for(int i=0;i<l;i++)
permutations(prefix+patt.charAt(i), patt.substring(0, i)+patt.substring(i+1, l));
}
public static boolean search(String text, String pattern)
{
for(int i=0;i<text.length()-pattern.length();i++)
{
int x = i;
int count = 0;
for(int j=0;j<pattern.length();j++,x++)
{
if(text.charAt(x) == pattern.charAt(j))
count++;
}
if(count == pattern.length())
return true;
}
return false;
}
}
class P13
{
static String text;
static boolean result = false;
public static void main(String[] args)
{
text = "badfcge";
String patt = "fcd";
permutations(patt);
System.out.println(result);
}
public static void permutations(String patt)
{
permutations("",patt);
}
public static void permutations(String prefix, String patt)
{
int l = patt.length();
if(l == 0)
{
//System.out.println(prefix);
if(search(text, prefix))
result = true;
}
for(int i=0;i<l;i++)
permutations(prefix+patt.charAt(i), patt.substring(0, i)+patt.substring(i+1, l));
}
public static boolean search(String text, String pattern)
{
for(int i=0;i<text.length()-pattern.length();i++)
{
int x = i;
int count = 0;
for(int j=0;j<pattern.length();j++,x++)
{
if(text.charAt(x) == pattern.charAt(j))
count++;
}
if(count == pattern.length())
return true;
}
return false;
}
}
An easy solution assuming alphabets from 'a' to 'z' allowed.
Time O(N)
Space O(1)
bool isSubstr(string s, string sub)
{
int l1 = s.length();
int l2 = sub.length();
if(l2 > l1)
return false;
string alpha2 = "00000000000000000000000000";
string alpha1 = "00000000000000000000000000";
for(int i = 0;i < l2;i++)
{
alpha1[sub[i] - 'a']++;
alpha2[s[i]-'a']++;
}
if(alpha2 == alpha1)
return true;
for(int i = 1;i +l2 < l1;i++)
{
printf("here\n");
alpha2[s[i-1]-'a']--;
alpha2[s[i+l2-1]-'a']++;
if(alpha2 == alpha1)
return true;
}
return false;
}
sorry a minute correction its i + l2 -1 < l1
bool isSubstr(string s, string sub)
{
int l1 = s.length();
int l2 = sub.length();
if(l2 > l1)
return false;
string alpha2 = "00000000000000000000000000";
string alpha1 = "00000000000000000000000000";
for(int i = 0;i < l2;i++)
{
alpha1[sub[i] - 'a']++;
alpha2[s[i]-'a']++;
}
if(alpha2 == alpha1)
return true;
for(int i = 1;i +l2 -1 < l1;i++)
{
alpha2[s[i-1]-'a']--;
alpha2[s[i+l2-1]-'a']++;
if(alpha2 == alpha1)
return true;
}
return false;
}
C++ solution is below. Only one inefficiency: you need to repopulate the hash every time you don't have match.
int StrLen(char *s)
{
int length = 0;
if (s)
{
while (*s)
{
length++;
s++;
}
}
return length;
}
void InitHash(int *hash, int hashSize, char *s)
{
if (hash && s)
{
for (int i = 0; i < hashSize; hash[i++] = 0);
while (*s)
{
hash[*s] += 1;
s++;
}
}
}
bool FindPermutation(char *str1, char *str2)
{
bool found = false;
int length2 = -1;
int i = -1;
int hash[256];
if (str1 && str2)
{
length2 = StrLen(str2);
InitHash(hash, 256, str2);
while (*str1)
{
for (i = 0; i < length2 && str1[i] != '\0'; i++)
{
if (hash[str1[i]] != 0)
{
hash[str1[i]]--;
}
else
{
break;
}
}
if (i == length2 || str1[i] == '\0')
{
// permutation is found
found = (i == length2);
break;
}
else
{
str1 += (i + 1);
InitHash(hash, 256, str2);
}
}
}
return found;
}
#include <iostream>
#include<algorithm>
#include<string>
using namespace std;
int main()
{
int n;
cin>>n;
cin.ignore();
for(int i=0;i<n;i++)
{
string p,t;
getline(cin,p);
getline(cin,t);
int lp=p.length();
int lt=t.length();
int fp[26]={0},ft[26]={0};
for(int i=0;i<lp;i++)
fp[p[i]-'a']++;
for(int i=0;i<lp;i++)
ft[t[i]-'a']++;
bool m;
for(int i=lp;i<=lt;i++)
{
m=true;
for(int j=0;j<26;j++)
if(fp[j]!=ft[j])
{
m=false;
break;
}
if(m)
break;
ft[t[i-lp]-'a']--;
ft[t[i]-'a']++;
}
if(m)
cout<<"YES\n";
else
cout<<"NO\n";
}
return 0;
}
Compute all the permutations of the smaller string(easily done recursively). For each permutation, check if it is a substring of bigger string.
public static void main(String[] args) throws Exception
{
String one = "abcdefg";
String two = "ba";
System.out.println(findifsubperumuation(one, two));
}
//Assumes one is longer than 2
public static boolean findifsubperumuation(String one, String two)
{
int k = two.length();
ArrayList<String> all;
for(int i=0; i<one.length() && i+k<one.length()+1; i++)
{
String current = one.substring(i, i+k);
all=permutation(current);
for(String perm : all)
{
if(perm.equals(two))
{
return true;
}
}
}
return false;
}
public static ArrayList<String> permutation(String s)
{
if(s.length()==1)
{
ArrayList<String> perms = new ArrayList<String>();
perms.add(s);
return perms;
}
ArrayList<String> permsother = permutation(s.substring(1));
ArrayList<String> perms = new ArrayList<String>();
String firstletter = s.substring(0,1);
for(String current : permsother)
{
for(int i=0; i<=current.length(); i++)
{
String Firstpart = current.substring(0,i);
String Secondpart = current.substring(i);
String together = Firstpart.concat(firstletter);
together=together.concat(Secondpart);
perms.add(together);
}
}
return perms;
}
I don't claim it's optimized but it will work,
1) I find all substring's in the first word that are the length of the second word.
2) I generate all the permutations for a substring of the first word
3) check every permutation i generate and compare it to the second word
O((n/k)(k)!), it's a horrible solution, but I already had the code for permutation. A better solution would be to look for every substring of size k in the longer string, and check that the number of occurrences of every letter is in this substring is same as the number of every occurrences of every letter in the smaller string.
HI i think this can be easily solved by Hash maps.
Create a hash map for the second string and keep incrementing for a new instance found for a letter. ex: abdds: a(1),b(1),d(2),s(1).
Then for the second string, keep decrementing if the same letter is found.
if the first string ends and all the letters have the values associtaed to them as zeroes: return TRUE.
The complexity is m+n, 1.e. of O(m)
The problem is same as finding the smallest window containing all the characters of a given string (here its 'ab'). If such a window is there return 'true'. Provide any alternate soln if there.
- Nascent March 02, 2013