Can you please review my code, it is showing TLE on the test case 10 which is not big enough for TLE. Also my code time complexity in the worst case will hopefully pass the test cases.
Thanks for your time.
Here is the algorithm (P.S. Pls ignore. it is messy.)
-
Create a map for string2.
-
For each index in string1 . Find if the character at index in string 1 is in string2 by
looking at map2.i) if it is not present then not gonna start from this index and continue to step 2(a) [e.g. starting from 'w'] ii) otherwise start from this index and find the window where all the characters of string2 present. a) While doing so if char is not in map2 then this char is extra char in window so avoid it b) otherwise this char is common in both string so add it to map1 then check if this char has equal freq in both string and hence check if all char has equal to more freq in map1 then in map2.
This is my code:
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s1, s2;
getline(cin, s1);
getline(cin, s2);
int n = s1.length();
map<char, int> mp1, mp2;
for (char c : s2)
{
auto it = mp2.find(c);
if (it != mp2.end())
{
int freq = it->second;
mp2[c] = freq + 1;
}
else
{
mp2[c] = 1;
}
}
int size = mp2.size();
int count = 0, minLen = INT_MAX;
string ans = "";
int startIndex = 0, endLen = 0;
for (int i = 0; i < n; i++)
{
//resetting map and count
count = 0;
mp1.clear();
//character not in map2
auto it2 = mp2.find(s1[i]);
if (it2 == mp2.end())
{
continue;
}
//character in map2
for (int j = i; j < n; j++)
{
char c = s1[j];
auto it3 = mp2.find(c);
//char commom in both string
if (it3 != mp2.end())
{
auto it = mp1.find(c);
if (it != mp1.end())
{
int freq = it->second;
mp1[c] = freq + 1;
}
else
{
mp1[c] = 1;
}
//frequency of one character found
if (mp1[c] == mp2[c])
{
count++;
}
//all char frequency matched
if (count == size)
{
int len = j - i + 1;
if (len < minLen)
{
minLen = len;
startIndex = i;
endLen = len;
}
break;
}
}
else
{
continue;
}
}
}
ans = s1.substr(startIndex, endLen);
if (ans == "")
{
cout << "No String\n";
}
else
{
cout << ans << "\n";
}
return 0;
}