Dollar Sign Deletion in a string using Java

4 min readDec 18, 2019

Source: AlgoDaily | Tags: String, Arrays, Stack

Problem Statement:

You’re given an array of strings containing alphabetical characters and certain $ characters. A $ represents a DELETE action whereby the character before it and the $ itself is deleted.

Each of these strings will be run through a method to operate on the $ DELETE action. We want to find out if the final string is the same for all of them.

Examples:
1. If the input string array is {“f$ec”, “ec$”} it should return false as the final string array after deletion is {“ec”, “e”}
2. If the input string array is {“f$ec”, “ec”} it should return true as the final string array after deletion is {“ec”, “ec”}
3. If the input string array is {“ ab$$”, “ c$d$”} it should return true as the final string array after deletion is {“”, “”}

Recommended to try out the solution first in your editor and then jump into solution :)

Solution Approach:

Approach 1:

This approach uses a stack data structure to modify the string as instructed in the problem statement and involves 2 steps which are clearly explained below.

Step 1:

Convert all the strings in the given string array by removing $ symbol as explained in the problem statement. This involves the following two sub-steps for each string in the array.

Sub-Step (a):

Use stack to delete the $ symbol and the preceding character in the string.

Sub-Step (b):

Once Sub-step (a) is done form the string with the remaining characters in the stack in reverse order.

Step 2:

Now loop over the converted String array and check whether all the strings are equal or not

Code:

package main.java.Practice;import java.util.Stack;public class DeleteDollar {   public static void main(String[] args) {
      String[] str = { "f$ec", "ec$" };
      System.out.println(isDollarDeleteEqual(str));
   }private static boolean isDollarDeleteEqual(String[] str) {
      for (int i = 0; i < str.length; i++) {
         str[i] = removeDollar(str[i]);
      }
     
      for (int i = 1; i < str.length; i++) {
         if (str[i].equalsIgnoreCase(str[i - 1]))
            continue;
         else
            return false;
      }
      return true;
   }
 
   private static String removeDollar(String str) {
      Stack<Character> s = new Stack<>();
      String s1 = "";
      for (int i = 0; i < str.length(); i++) {
         if (str.charAt(i) == '$' && !s.isEmpty()) {
            s.pop();
         } else if (str.charAt(i) == '$' && s.isEmpty()) {
            continue;
         } else {
            s.push(str.charAt(i));
         }
      }
      while (!s.isEmpty()) {
         s1 = s1 + s.pop();
      }
      s1 = reverse(s1);
      return s1;
   }   static String reverse(String s) {
      int l = s.length();
      char[] ch = s.toCharArray();
      for (int i = 0; i < l / 2; i++) {
         char t = ch[i];
         ch[i] = ch[l - i - 1];
         ch[l - i - 1] = t;
      }
      return new String(ch);
   }
}

Time Complexity: As we are looping around the array of strings it takes O(N) time and for each string to do the $ delete operation and to create a new string with remaining characters it takes O(M) time per string where M is the length of the longest string in the given string array. So the total time complexity of the program is O(N*M).

Space Complexity: As we are using the stack for the delete operation and char array to create a modified string, it takes O(M+M) space where M is the length of the longest string in the given string array. So the total space complexity of the program is O(M).

Approach 2:

In the above approach, the code part where we are modifying the string is contributing much to space complexities.

We can decrease the overall space complexity to O(1) with this approach.

Here we use an integer counter and a new string variable to modify each string and replace it in the given array. Follow the below rules for this approach.

Rule 1: We loop around the characters in the string in reverse order and increment this counter whenever we encounter a $ symbol in the string.

Rule 2: If we encounter an alphabet or number in the string and if the counter value is greater than 0, we decrement the counter value.

Rule 3: If we encounter an alphabet or number in the string and if the counter value is less than 0, we append the character to the created new string

Code:

package main.java.Practice;public class DeleteDollarOptimized {
   static String s = "";    public static void main(String[] args) {
       String[] str = { "f$ec", "ec$" };
       System.out.println(isDollarDeleteEqual(str));
    }    private static boolean isDollarDeleteEqual(String[] str) {
       for (int i = 0; i < str.length; i++) {
          str[i] = removeDollar(str[i]);
       }
  
       for (int i = 1; i < str.length; i++) {
          if (str[i].equalsIgnoreCase(str[i - 1]))
             continue;
          else
             return false;
       }
      
       return true;
    }    private static String removeDollar(String str) {
       int counter = 0;
       s = "";
       for (int i = str.length() - 1; i >= 0; i--) {
          if (str.charAt(i) == '$')
             counter++;
          else {
             if (counter > 0)
                counter--;
             else
                s = str.charAt(i)+s;
          }
      }
     
      return s;
   }
}

Space Complexity: As we are using an integer variable and global string variable for modifying the given string whose size will always be constant, so the total space complexity can be treated as O(1)

Dollar Sign Deletion in a string using Java

Problem Statement:

Solution Approach:

Approach 1:

Code:

Approach 2:

Code:

These are a few workable approaches. If you have any other solution, please feel free to provide it in response to this post.

Written by Vishnu Lakkimsetty