# Minus Minus is Plus

Strings

Medium

#### Problem Statement (Simplified):

Given two string `S` and `T` containing only `-` and `+`. Two `-` together can form a single `+`. If it is possible to obtain `T` from 'S' then print `YES` else `NO`.

See original problem statement here

#### Test Case

``````Input:
4
-+--+
-+++
--------
-+--+-
--
---
+++
+++

Output:
YES
YES
NO
YES

Explanation:
Case-1:
Here we can see if we convert '--' starting at index 2 to '+', string S becomes string T. So YES string S can become string T.

Case-2:
Here we can see, if we convert '--' starting at index 1 to '+', also a string '--' starting at index 5 is converted to '+', string S becomes string T.So YES string S can become string T.

Case-3:
Here we can see if we convert '--' starting at index 2 to '+', string S becomes string T.

Case-4:
Here we can see, String S is smaller than string T. So it can never become string T.``````

#### Solving Approach :

> 1) If the length of `T` is larger than `S`, it is impossible to obtain `T` from `S`. So we set flag value to `False` according to the fundamentals of data structures in c++.
> 2) Otherwise, we iterate over both strings, during iteration we can get three cases :
>> 1) If both `S` and `T` have the same characters at the current position, we continue the iteration.
>>2) If `S` contains `+` and `T` contains `-` at the same positions, that means we cannot achieve `T` from `S`, so we end iterations here and set flag value to `False`.
>>3) If `S` contains `-` and `T` contains `+` at the same position, we check if next position contains `-` or not in `S`, if yes we move forward and increase the `S` position by 1 as both `-` count as a single `+`, otherwise we get out of iterations and set flag value to `False`.

3) After we have iterated, we check if the final position of `S` and `T` are equal or not. If the iteration was completed and both ended at the same point that means `T` can be achieved by `S` so we set flag value `True`.
4) We finally check the flag value, if it is `False` we print "`YES`", else "`No`".

## Example

• Lets assume String `S` to be `'--------'` and string `T` to be `'-+--+-'`.
• Here `S` is larger in length than `T`, so we can move further.
• If we dry run the approach given above, we can check if they can become same or not. We start from starting point of both strings, using two pointers, `i=0` and `j=0`. Now, we iterate both strings one by one.

Step-1:
> > Here, we see both characters at both indexes `i` and `j` are `'-'`, so we move further.
>
Step-2:
> > Here, we see character at index `i` is `'-'` and character at index `j` is `'+'`, so we check if next character to `i` is `'-'` or not. In this case, it is `'-'`, so we can convert these two `'-'` to a `'+'`. We move index `i` by one more step too because two `'-'` are consumed to form a `'+'`.
>
Step-3:
> > Here, we see both characters at both indexes `i` and `j` are `'-'`, so we move further.
>
Step-4:
> > Here, we see both characters at both indexes `i` and `j` are `'-'`, so we move further.
>
Step-5:
> > Here, we see character at index `i` is `'-'` and character at index `j` is `'+'`, so we check if next character to `i` is `'-'` or not. In this case, it is `'-'`, so we can convert these two `'-'` to a `'+'`. We move index `i` by one more step too because two `'-'` are consumed to form a `'+'`.
>
Step-6:
> > Here, we see both characters at both indexes `i` and `j` are `'-'`, so we move further.
>

• After `step-6`, both of our strings are traversed, so `YES`, string `S` can become string `T`.

## Solutions

```
#include <stdio.h>

int main()
{
int test;
scanf("%d",&test);

while(test--){

char s,t;
scanf("%s%s",s,t);

int diff = 0;
int flag = 0;

if((strlen(s)==0 && strlen(t)==0) || (strlen(s) < strlen(t)))
flag = 0;
else{
for(int i=0; (i-diff)<strlen(t); i++){
if(t[i-diff] == '+' && s[i] == '-' && s[i+1] == '-'){
i++;
diff++;

}else if((t[i-diff] == '+' && s[i] == '+') || (t[i-diff] == '-' && s[i] == '-') ){
flag = 0;
}
else{
flag = 1;
break;
}
}
}

if((strlen(s)-diff) != strlen(t)){
flag = 1;
}

if(flag)
printf("NO\n");
else
printf("YES\n");

}
}
```
```#include <bits/stdc++.h>
using namespace std;

int main()
{
int test;
cin>>test;

while(test--){

string s,t;
cin>>s>>t;

int diff = 0;
bool flag = false;

if((s.length()==0 && t.length()==0) || (s.length() < t.length()))
flag = false;
else{
for(int i=0; (i-diff)<t.length(); i++){
if(t[i-diff] == '+' && s[i] == '-' && s[i+1] == '-'){
i++;
diff++;

}else if((t[i-diff] == '+' && s[i] == '+') || (t[i-diff] == '-' && s[i] == '-') ){
flag = false;
}
else{
flag = true;
break;
}
}
}

if((s.length()-diff) != t.length()){
flag = true;
}

if(flag)
cout<<"NO"<<endl;
else
cout<<"YES"<<endl;

}
}

```
```
import java.util.*;
import java.io.*;

public class Main {
public static void main(String args[]) throws IOException {
Scanner sc= new Scanner(System.in);
int test_cases;
test_cases = sc.nextInt();

while(test_cases != 0){

String s = sc.next();
String t = sc.next();

int diff = 0;
int flag = 0;

if((s.length()==0 && t.length()==0) || (s.length() < t.length())){
flag = 0;
}
else{
for(int i=0; (i-diff)<t.length(); i++){
if(t.charAt(i-diff) == '+' && s.charAt(i) == '-'&& s.charAt(i+1) == '-' ){
i++;
diff++;

}else if((t.charAt(i-diff) == '+' && s.charAt(i) == '+') || (t.charAt(i-diff) == '-' && s.charAt(i) == '-') ){
flag = 0;
}
else{
flag = 1;
break;
}
}
}

if((s.length()-diff) != t.length()){
flag = 1;
}

if(flag == 1)
System.out.println("NO");
else
System.out.println("YES");

test_cases--;

}
}
}
```

Space Complexity of this approach would be `O(1).`