I saw a variation of this question. Problem Statement: Keyboard Caps Lock is not working. Given a sentence, write a program that will act as a Caps Lock button. Whenever you encounter "caps lock" it mean that user pressed the caps lock button. Assume initially caps lock = OFF EX: tech caps lock dose caps lock is the caps lock best O/P: tech DOSE is the BEST
@@sairamkandgule3365 Initially caps_lock = 0 1st caps lock occurs before "dose" so caps_lock = 1 o/p "DOSE" Now caps lock is ON; just like our keyboard. So 2nd time when you press the caps lock, it'll switch of the Caps Lock caps_lock = 0 2nd "caps lock" is after "dose" so until it encounter the 3rd/next caps lock; it'll print everything in lowercase.
string concatenation is O(n^2) in time complexity. but a lot of people think it’s O(n). So your solution is O(n^2 + m^2). If you have used an array or stack then it would have been O(n+m)
It wont make any sense if just adding a character the end of string took O(N) time. It will take time equals no of new characters being added. Read append in this blog and let me know if it's wrong; www.hackerearth.com/practice/notes/standard-template-library/
@@NikhilKumar-oy7mx leetcode.com/problems/backspace-string-compare/discuss/572179/easily-explained-and-0-ms-faster-than-10000-of-c-submissions read this
hey i think you should upload the solution of Leetcode daily challenge on the next day after the contest is over...someone may report this...altho very nice explanation!!..keep it up
No, you cannot report this bacause the problems are already available on leetcode and other websites. Solutions are also available. This contest is only meant for practice using previously uploaded problems. These are not new problems for anyone to claim.
Mohit Ishpunyani The concept is very well explained in this video infact i have my channel which has similar content.pls check, subscribe and show me your support if u like them and give me u r feedback in comment section.thank you:)
Can someone explain me how will this handle the case such as "ab##c". The string after removing # according to the question should be "ac" but I feel the approach in the video would give "c" as the resultant string.
If you type ab and then give 2 backspaces then your string will now be empty. Now if you type c then your string will be c. So yes, the result is c. # means backspace and ## means 2 times backspaces.
Here is the code with O(1) space class Solution { public boolean backspaceCompare(String s, String t) { int i = 0; while (i < s.length()) { if (s.charAt(i) != '#') { i++; } else { if (i == 0) { s = s.substring(i + 1); } else { String pa = s.substring(0,i - 1); String pb = ""; if (i + 1 < s.length()) pb = s.substring(i + 1); s = pa + pb; i = pa.length(); } } } i=0; while (i < t.length()) { if (t.charAt(i) != '#') { i++; } else { if (i == 0) { t = t.substring(i + 1); } else { String pa = t.substring(0,i - 1); String pb = ""; if (i + 1 < t.length()) pb = t.substring(i + 1); t = pa + pb; i = pa.length(); } } } return s.equals(t); } }
we can do the problem in 0(1) space and o{m+n) complexity by traversing both the strings from back code: class Solution { public boolean backspaceCompare(String S, String T) { int i = S.length() - 1, j = T.length() - 1; int skipS = 0, skipT = 0; while (i >= 0 || j >= 0) { // While there may be chars in build(S) or build (T) while (i >= 0) { // Find position of next possible char in build(S) if (S.charAt(i) == '#') {skipS++; i--;} else if (skipS > 0) {skipS--; i--;} else break; } while (j >= 0) { // Find position of next possible char in build(T) if (T.charAt(j) == '#') {skipT++; j--;} else if (skipT > 0) {skipT--; j--;} else break; } // If two actual characters are different if (i >= 0 && j >= 0 && S.charAt(i) != T.charAt(j)) return false; // If expecting to compare char vs nothing if ((i >= 0) != (j >= 0)) return false; i--; j--; } return true; } SIr ,small doubt how you are managing your time with your job and youtube content.Beacuse although video length will be on average 15min it may take 1 to 2 hours to complete editing stufff and finalize the video?
c++ code in o(1) space ,o(m+n) complexity int i=S.length()-1, skipS=0,skipT=0; int j=T.length()-1; while(i>=0||j>=0){ while(i>=0){ if(S[i]=='#'){skipS++;i--;} else if(skipS>0){skipS--;i--;} else break; }
Actually it will not be possible to make this video again as too many other imp videos are pending. The trick for O(1) space is simple. You can easily do it in 2 traversals for better understanding. In first traversal from left to right, balance all closing brackets using opening brackets + stars and 2nd traversal from right left, balance all opening brackets using stars and closing brackets already seen :) Try it once. If you find confusion then I will clear your doubt.
@@techdose4u well I guess u are talking about some other problem , btw I have tried with shift string in every iteration and match but it says time exceed , I iterate string in reverse check for match if char if # I skip no of times # appear
My bad. I was thinking about balancing brackets. Iterate the string from end to start. As soon as you see a backspace, keep a counter for it. Now as you encounter a char, check if counter is zero. If counter > 0 then ignore the current character. Do this for both strings. Whenever you find a non-skippable character, it should be equal, otherwise strings won't be equal. Solution is given on leetcode solutions section. If you have any doubt then let me know.
It checks the result1 string is empty or not. If the result1 string is empty then we can't perform the result1.pop_back() and it'll give you a run time error.
I saw a variation of this question.
Problem Statement:
Keyboard Caps Lock is not working.
Given a sentence, write a program that will act as a Caps Lock button.
Whenever you encounter "caps lock" it mean that user pressed the caps lock button.
Assume initially caps lock = OFF
EX: tech caps lock dose caps lock is the caps lock best
O/P: tech DOSE is the BEST
Is this question on LeetCode too?
@@spetsnaz_2 Don't know but my friend asked for the solution so I thought it's similar to the question in video.
I think the output should be: tech DOSE IS the BEST
@@sairamkandgule3365 tech DOSE IS THE best
@@sairamkandgule3365
Initially caps_lock = 0
1st caps lock occurs before "dose" so
caps_lock = 1
o/p "DOSE"
Now caps lock is ON; just like our keyboard.
So 2nd time when you press the caps lock, it'll switch of the Caps Lock
caps_lock = 0
2nd "caps lock" is after "dose" so until it encounter the 3rd/next caps lock; it'll print everything in lowercase.
Sir you are the best hamesha eese hi aapne students keliye video bnate rhe
Time complexity is wrong, it should O(n^2). You building 2 new strings which would be O(n^2) but asymptotically you are right.
Building 2 strings is (N+M) and not NM.
string concatenation is O(n^2) in time complexity. but a lot of people think it’s O(n). So your solution is O(n^2 + m^2). If you have used an array or stack then it would have been O(n+m)
It wont make any sense if just adding a character the end of string took O(N) time. It will take time equals no of new characters being added. Read append in this blog and let me know if it's wrong; www.hackerearth.com/practice/notes/standard-template-library/
@@IfegunniObiajulu u better give a serious explanation for this ,it doesnt make sense.........,where u read this....
Java is O(n^2)
Good one !
Can be done using Stack also.
stack will make space complexity O(n)
@@RajatSingh-dg8ov i also tried using stack but there was some kind of memory error.
@@NikhilKumar-oy7mx leetcode.com/problems/backspace-string-compare/discuss/572179/easily-explained-and-0-ms-faster-than-10000-of-c-submissions
read this
class Solution {
public:
bool backspaceCompare(string S, string T) {
stacks1,s2;
for(char i : S ){
if(i='a'){
s1.push(i);
}else{
if(!s1.empty()){
s1.pop();
}
}
}
for(char i : T ){
if(i='a'){
s2.push(i);
}else{
if(!s2.empty()){
s2.pop();
}
}
}
if(s1==s2)
return true;
return false;
}
};
O(m+n) with O(1) solution -
bool backspaceCompare(string s, string t) {
int sizeS = s.size(), sizeT = t.size(), i = 0;
while (i < sizeS) {
if(s[i] == '#' and i < 1){
s.erase(s.begin()+i, s.begin()+i+1);
sizeS--;
continue;
}
else if(s[i] == '#'){
s.erase(s.begin()+i-1, s.begin()+i+1);
i -= 1;
sizeS -= 2;
}
else
i++;
}
i = 0;
while (i < sizeT) {
if(t[i] == '#' and i < 1){
t.erase(t.begin()+i, t.begin()+i+1);
sizeT--;
continue;
}
else if(t[i] == '#'){
t.erase(t.begin()+i-1, t.begin()+i+1);
i -= 1;
sizeT -= 2;
}
else
i++;
}
return s == t;
}
hey i think you should upload the solution of Leetcode daily challenge on the next day after the contest is over...someone may report this...altho very nice explanation!!..keep it up
No, you cannot report this bacause the problems are already available on leetcode and other websites. Solutions are also available. This contest is only meant for practice using previously uploaded problems. These are not new problems for anyone to claim.
@@techdose4u alright man....it was all in good sense I thought that someone might do..also what u say is correct..i take back my statement
😅
Can we get it done in O(1)space, just doing it in-place? I'll appreciate the fact if you do so.
Mohit Ishpunyani The concept is very well explained in this video infact i have my channel which has similar content.pls check, subscribe and show me your support if u like them and give me u r feedback in comment section.thank you:)
Can someone explain me how will this handle the case such as "ab##c". The string after removing # according to the question should be "ac" but I feel the approach in the video would give "c" as the resultant string.
If you type ab and then give 2 backspaces then your string will now be empty. Now if you type c then your string will be c. So yes, the result is c. # means backspace and ## means 2 times backspaces.
@@techdose4u thanks for clearing sir.
@@techdose4u thanks for clearing sir.
Approach is good but sir instead of writing same code twice we can create a method & pass s1 & s2.
Yea sure :)
Nice 😊 problem..
I really like this
Nice :)
Here is the code with O(1) space
class Solution {
public boolean backspaceCompare(String s, String t) {
int i = 0;
while (i < s.length()) {
if (s.charAt(i) != '#') {
i++;
} else {
if (i == 0) {
s = s.substring(i + 1);
} else {
String pa = s.substring(0,i - 1);
String pb = "";
if (i + 1 < s.length()) pb = s.substring(i + 1);
s = pa + pb;
i = pa.length();
}
}
}
i=0;
while (i < t.length()) {
if (t.charAt(i) != '#') {
i++;
} else {
if (i == 0) {
t = t.substring(i + 1);
} else {
String pa = t.substring(0,i - 1);
String pb = "";
if (i + 1 < t.length()) pb = t.substring(i + 1);
t = pa + pb;
i = pa.length();
}
}
}
return s.equals(t);
}
}
question is to do in O(n) but you did it in O(2n)!
I think you miscalculated the time complexity. Let me know if you have doubt regarding it.
Thank you for your explanation. Follow up : Can you solve it in O(N) time and O(1) space? May I ask how do we do that ?
Need to check it. Forgot the statement :P lol
we can do the problem in 0(1) space and o{m+n) complexity by traversing both the strings from back
code:
class Solution {
public boolean backspaceCompare(String S, String T) {
int i = S.length() - 1, j = T.length() - 1;
int skipS = 0, skipT = 0;
while (i >= 0 || j >= 0) { // While there may be chars in build(S) or build (T)
while (i >= 0) { // Find position of next possible char in build(S)
if (S.charAt(i) == '#') {skipS++; i--;}
else if (skipS > 0) {skipS--; i--;}
else break;
}
while (j >= 0) { // Find position of next possible char in build(T)
if (T.charAt(j) == '#') {skipT++; j--;}
else if (skipT > 0) {skipT--; j--;}
else break;
}
// If two actual characters are different
if (i >= 0 && j >= 0 && S.charAt(i) != T.charAt(j))
return false;
// If expecting to compare char vs nothing
if ((i >= 0) != (j >= 0))
return false;
i--; j--;
}
return true;
}
SIr ,small doubt how you are managing your time with your job and youtube content.Beacuse although video length will be on average 15min it may take 1 to 2 hours to complete editing stufff and finalize the video?
c++ code in o(1) space ,o(m+n) complexity
int i=S.length()-1, skipS=0,skipT=0;
int j=T.length()-1;
while(i>=0||j>=0){
while(i>=0){
if(S[i]=='#'){skipS++;i--;}
else if(skipS>0){skipS--;i--;}
else
break;
}
while(j>=0){
if(T[j]=='#'){skipT++;j--;}
else if(skipT>0){skipT--;j--;}
else
break;
}
if(i>=0 && j>=0 && S[i]!=T[j])return false;
if((i>=0)!=(j>=0))
return false;
i--;j--;
}
return true;
Keep uploading sir.🙌👌
Yes I will.
Can u make video with 0(1) space ?
Actually it will not be possible to make this video again as too many other imp videos are pending. The trick for O(1) space is simple. You can easily do it in 2 traversals for better understanding. In first traversal from left to right, balance all closing brackets using opening brackets + stars and 2nd traversal from right left, balance all opening brackets using stars and closing brackets already seen :) Try it once. If you find confusion then I will clear your doubt.
@@techdose4u well I guess u are talking about some other problem , btw I have tried with shift string in every iteration and match but it says time exceed , I iterate string in reverse check for match if char if # I skip no of times # appear
My bad. I was thinking about balancing brackets. Iterate the string from end to start. As soon as you see a backspace, keep a counter for it. Now as you encounter a char, check if counter is zero. If counter > 0 then ignore the current character. Do this for both strings. Whenever you find a non-skippable character, it should be equal, otherwise strings won't be equal. Solution is given on leetcode solutions section. If you have any doubt then let me know.
Can we get it done in O(1)space, just doing it in-place? I'll appreciate the fact if you do so,
Use erase library to do this inppace.
Yes we can do.
Start comparing the strings from the right.
When you come across # you just skip # and character before #.
Sir
Else if(r1.empty())
Ka kya work he yaha oe
It checks the result1 string is empty or not. If the result1 string is empty then we can't perform the result1.pop_back() and it'll give you a run time error.
The pop_back() only works if the result1 string is not empty!
This solution not accepted Some case are accepted and some not accepted
Please share your code in COMMENT for everyone to see and help.
Anyone with O(1) space complexity ???
You can erase characters in original string using if-else statement and can achieve O(1) space complexity.
use stack
Yes you can :)
JAVA version Time-O(n) && Space- O(1)
class Solution
{
public boolean backspaceCompare(String s, String t)
{
StringBuffer res1=new StringBuffer();
StringBuffer res2=new StringBuffer();
for(int i=0;i='a'&&s.charAt(i)=1)
res1.deleteCharAt(res1.length()-1);
}
}
for(int i=0;i='a'&&t.charAt(i)=1)
res2.deleteCharAt(res2.length()-1);
}
}
if(res1.compareTo(res2)==0)
return true;
return false;
}
}