Minus Minus is Plus

Concepts Used

Strings

Difficulty Level

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[10000001],t[10000001];
        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).

Previous post Hometown Newspaper
Next post Aman and Shopping

Leave a Reply

Your email address will not be published. Required fields are marked *