Thank you for a wonderful explanation. I tried implementing with python def shortestSubstring(s): n = len(s) k = len(set(s)) start = 0 end = 0 count = 0 hashmap = dict() ans_str = "" min_len = 10**9 + 7
while end < n: curr_ch = s[end] if curr_ch in hashmap: hashmap[curr_ch] += 1
else: hashmap[curr_ch] = 1 count += 1
if count == k: if min_len > (end - start + 1): min_len = end - start + 1 ans_str = s[start: end+1]
code is simpe as ip address must be of length 12 so we use loop of 3,4,4 it will give right ans #include using namespace std; vectorvalid(string s) { vector ans; if(s.length()12) return ans; for(int i=0;i1) continue; if(d[0]=='0'&&d.length()>1) continue; if(stoi(a)
If it was greater than 1 then count of distinct characters won't change , but if it is 1 after decrement it becomes 0 which means now we dont have all the unique cahracters
// For all those who did not get it (implementation) class Solution{ public: const int no_of_chars = 256; // Function to find smallest window containing // all characters of 'pat' string findSubString(string str) {
int len1 = str.length(); string pat = "";
set s; for (int i = 0; i < len1; i++) s.insert(str[i]); for (auto i = s.begin(); i != s.end(); i++) pat += (*i);
int len2 = pat.length();
// check if string's length is less than pattern's // length. If yes then no such window can exist if (len1 < len2) { return ""; }
int hash_pat[no_of_chars] = {0}; int hash_str[no_of_chars] = {0};
// store occurrence ofs characters of pattern for (int i = 0; i < len2; i++) hash_pat[pat[i]]++;
int start = 0, start_index = -1, min_len = INT_MAX;
// start traversing the string int count = 0; // count of characters for (int j = 0; j < len1; j++) { // count occurrence of characters of string hash_str[str[j]]++;
// If string's char matches with pattern's char // then increment count if (hash_pat[str[j]] != 0 && hash_str[str[j]] hash_pat[str[start]] || hash_pat[str[start]] == 0) {
if (hash_str[str[start]] > hash_pat[str[start]]) hash_str[str[start]]--; start++; }
// If no window found if (start_index == -1) { return ""; }
// Return substring starting from start_index // and length min_len return str.substr(start_index, min_len); } }; //Although his approach is great but the implementation is wrong
Working Solution in Java for Smallest distinct window gfg: class Solution { public String findSubString(String str) { Map map = new HashMap(); Set set = new HashSet(); for (char c : str.toCharArray()) { set.add(c); } int i = 0, j = 1; int n = set.size(); for (Character ch : set) { map.put(ch, 0); } map.put(str.charAt(i), 1); int c = 0; c++; int start = 0, end = 0; int mi = Integer.MAX_VALUE; while (i
![[Full] 4 ต่อ 4 Celebrity EP.920 | 3 พ.ย. 67 | one31](http://i.ytimg.com/vi/KwiW2M_kAg4/mqdefault.jpg)
Thank you for a wonderful explanation. I tried implementing with python
def shortestSubstring(s):
n = len(s)
k = len(set(s))
start = 0
end = 0
count = 0
hashmap = dict()
ans_str = ""
min_len = 10**9 + 7
while end < n:
curr_ch = s[end]
if curr_ch in hashmap:
hashmap[curr_ch] += 1
else:
hashmap[curr_ch] = 1
count += 1
if count == k:
if min_len > (end - start + 1):
min_len = end - start + 1
ans_str = s[start: end+1]
while count == k:
if min_len > (end - start + 1):
min_len = (end - start + 1)
ans_str = s[start: end+1]
hashmap[s[start]] -= 1
if hashmap[s[start]] == 0:
count -= 1
del hashmap[s[start]]
start += 1
end += 1
#print(min_len)
return ans_str
t = int(input())
while t > 0:
s = input()
print(shortestSubstring(s))
t = t-1
It won't work when the given pattern doesn't have all distinct element of the given string, or when repeated element are present in the pattern.
How time complexity ooder of n here j goes till last index and due to srink i also can go last index .
Run time error comes
It is giving TLE on GFG.
Time limit exceeded error in gfg website
Can you provide more optimized solution of this problem?
is it still showing tle??
it is cause you are using set and uski time complexity is nlogn
so use unordered set which usually performs operations in O(1)
thanks bro was facing the same problem n it worked....@@romilpatel6227
Java implementation for the updated question:
public static String smallestWindow(String s, String p){
int n=s.length();
int m=p.length();
if(m>n){
return "-1";
}
if(m==n){
return s.equals(p)?p:"-1";
}
HashMap pm=new HashMap();
for(int i=0;i0){
ctz--;
}
i++;
}
}
j++;
}
if(st==-1){
return "-1";
}
return s.substring(st,e+1);
}
Java🤮🤮🤮
bhaiya ip address vaala karva do if possible, it is at index 87 in the excel sheet
+1
code is simpe as ip address must be of length 12 so we use loop of 3,4,4 it will give right ans
#include
using namespace std;
vectorvalid(string s)
{
vector ans;
if(s.length()12)
return ans;
for(int i=0;i1)
continue;
if(d[0]=='0'&&d.length()>1)
continue;
if(stoi(a)
@@devratnasawaitul8844 Do u know how to do this question with backtracking instead of nested for loops???
how can someone learn each and every questions like him, no valid explanation just learnt the solutions
tle
Verrryyyy Good Solution :))
you remove all a , you should not remove all charactor of a . suppose a does not come at the end then your code could be wrong.
Why you are decrementing when the count is 1 it may be more than 1 also right?
Solution is Not covered all Corner Cases.......SHOULD IMPROVED FOR UPDATED QUE
Why u are just decrement count if m[s[i]]==1 , as if it is greater then also we have to decrement count right?
If it was greater than 1 then count of distinct characters won't change , but if it is 1 after decrement it becomes 0 which means now we dont have all the unique cahracters
Nicely explained
// For all those who did not get it (implementation)
class Solution{
public:
const int no_of_chars = 256;
// Function to find smallest window containing
// all characters of 'pat'
string findSubString(string str) {
int len1 = str.length();
string pat = "";
set s;
for (int i = 0; i < len1; i++)
s.insert(str[i]);
for (auto i = s.begin(); i != s.end(); i++)
pat += (*i);
int len2 = pat.length();
// check if string's length is less than pattern's
// length. If yes then no such window can exist
if (len1 < len2) {
return "";
}
int hash_pat[no_of_chars] = {0};
int hash_str[no_of_chars] = {0};
// store occurrence ofs characters of pattern
for (int i = 0; i < len2; i++) hash_pat[pat[i]]++;
int start = 0, start_index = -1, min_len = INT_MAX;
// start traversing the string
int count = 0; // count of characters
for (int j = 0; j < len1; j++) {
// count occurrence of characters of string
hash_str[str[j]]++;
// If string's char matches with pattern's char
// then increment count
if (hash_pat[str[j]] != 0 && hash_str[str[j]] hash_pat[str[start]] ||
hash_pat[str[start]] == 0) {
if (hash_str[str[start]] > hash_pat[str[start]])
hash_str[str[start]]--;
start++;
}
// update window size
int len_window = j - start + 1;
if (min_len > len_window) {
min_len = len_window;
start_index = start;
}
}
}
// If no window found
if (start_index == -1) {
return "";
}
// Return substring starting from start_index
// and length min_len
return str.substr(start_index, min_len);
}
};
//Although his approach is great but the implementation is wrong
It is giving TLE on GFG can we optimize it more .
Make sure you are using unordered map.
thanks for your awesome explanation 🔥🔥
Working Solution in Java for Smallest distinct window gfg:
class Solution {
public String findSubString(String str) {
Map map = new HashMap();
Set set = new HashSet();
for (char c : str.toCharArray()) {
set.add(c);
}
int i = 0, j = 1;
int n = set.size();
for (Character ch : set) {
map.put(ch, 0);
}
map.put(str.charAt(i), 1);
int c = 0;
c++;
int start = 0, end = 0;
int mi = Integer.MAX_VALUE;
while (i
Confusing
what is tc and sc for this qn
\
awesome work
bhai question kya pucha hai tum solve kya karr rahe ho.
Bro please give the solution of the same program in c language 🙏
Not satisfied all test case of gfg
Thanks :)
thank you byaa
Nice video bro.
His accent is so irritating....
getting tle......
longest common subsequence bna do jaldi
This is a dynamic programming question so we will make this questions video in dynamic programming section.
th-cam.com/video/4Urd0a0BNng/w-d-xo.html
follow this link to understand lcs problem
Watch lcs by pepcoding, best explanation
Why we are not incrementing the value of "a" bt we are incrementing the count of rest ones " b" , " c"?
He forgot to do that , later he changed it.
Brother : In the excel sheet its about finding all character not at-least 1 character :
Kindly look into this
Find the shortest substring in a given string that contains all the characters of a given word
Tell me answer in today night
string findSubString(string str)
{
// Your code goes here
unordered_map mymap;
set st;
for(int i=0;i