Minus Minus is Plus

Last Updated on January 2, 2023 by Prepbytes

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.
2. Otherwise, we iterate over both strings, during iteration we can get three cases :
   • If both S and T have the same characters at the current position, we continue the iteration.
   • 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.
   • 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--;

        }
      }
    }

for _ in range(int(input())):
	s = input()
	t = input()
	diff = 0
	flag = False

	if len(s) == 0 and len(t) == 0 or len(s) < len(t):
		flag = False

	else:

		for i in range(len(t) + diff):
			
			if t[i - diff] == "+" and s[i] == "-" and s[i] == "-":
				i += 1
				diff += 1

			elif (t[i - diff] == "+" and s[i] == "+") or (t[i - diff] == "-" and s[i] == "-"):
				flag = False

			else:
				flag = True
				break


	if len(s) - diff != len(t):
		flag = True

	if flag:
		print("NO")

	else:
		print("YES")

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

This article tried to discuss Strings. Hope this blog helps you understand and solve the problem. To practice more problems on Strings you can check out MYCODE | Competitive Programming.