Backspace string compare | Leetcode #844

This video explains the day-9 problem of leetcode april coding challenge 2020. This is an easy level problem and i have shown the optimal approach to solve it. CODE LINK is given below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

[mihirsinghsolanki]

Sir you are the best hamesha eese hi aapne students keliye video bnate rhe

[crimsoncad]

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

[competitivedoritos]

Can we get it done in O(1)space, just doing it in-place? I'll appreciate the fact if you do so.

[chitrasomasingh]

Good one !
Can be done using Stack also.

[competitivedoritos]

Can we get it done in O(1)space, just doing it in-place? I'll appreciate the fact if you do so,

[IfegunniObiajulu]

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.

[yitingg]

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 ?

[rahulvig]

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.

[najimali]

Approach is good but sir instead of writing same code twice we can create a method & pass s1 & s2.

[mihirsinghsolanki]

Sir
Else if(r1.empty())
Ka kya work he yaha oe

[prachurjyabasistha]

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

[spetsnaz_]

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;
}

[trineshreddybs]

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?

[topcoder]

This solution not accepted Some case are accepted and some not accepted

[rajeshbammidy]

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);


}
}

[padigelajayanth]

question is to do in O(n) but you did it in O(2n)!

[guyswapnil]

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<s.length();i++)
{

res1.append(s.charAt(i));
else{
if(res1.length()>=1)

}
}
for(int i=0;i<t.length();i++)
{

res2.append(t.charAt(i));
else{
if(res2.length()>=1)

}
}
if(res1.compareTo(res2)==0)
return true;
return false;
}

}