Road to Google – Part 4 Typed Out Strings Ⅱ: Optimal Solution

Here’s the second part of Typed Out Strings, and as always, we’ll explore the best way to solve the problem: optimal solution.

Question:

Given two strings S and T, return if they equal when both are typed out. Any ‘#’ that appears in the string counts as a backspace.

Here, you’ve given the two strings: S:”abc#d” T:”abzz##d”.

As we did before, we can use dual printers to loop through both strings (image 02).

However, here’s the problem. When the pointer in S hits the character “C”, another pointer in T hits “z” and they don’t match (image 03). In this scenario, this loop solution doesn’t work.

Then what are you going to do?

Here’s one possible solution – why don’t you start looping from the other way around?

From here, let’s call the two pointers P1 and P2 respectively.

In the case when P1 and P2 hist #, there’s no point you need to compare since it’s not an alphanumeric character (image 05).

Let’s give attention to P1. When the pointer hits #, you know it deletes the next character, so we jump by 2 and reach character b – it’s because # deletes the nest character. But we can’t simply delete the next one since it could be another # as you can see in P2.

Here, let’s take a look at P2. P2 hits #, so you know you need to move by 2. So, you need a step-counter that is by now 2.

Now, P2 is moved to the next #, and you consume 1 step counter.

Here, you ask yourself is this # or another alphanumeric character? No, it’s not – it’s another #. SO you need to add 2 to the step counter.

Now, the step counter is increased to 3.

Then P2 moves to z consuming 1 step counter, and ask yourself – is this an alphanumeric character or #? It’s a character.

P2 now moves to the second z and ask yourself the same question. It’s an alphanumeric character. So it consumes another step counter.

Here, the step counter is consumed and it’s zero. And ask yourself the same question – is this an alphanumeric character or #? It’s a character.

Now, we’re at the pointer where we can compare the characters of both P1 and P2. Do they match – yes they do.

Finally, we compare the last remaining character of the two. Do they match – yes they do.

Coding solution:

So, here’s a code I can think of to solve the problem:

import java.io.*;

public class TypedOutStringOS {
    public static boolean backspaceCompare(String s, String t)  {
        int i = s.length() - 1;
        int j = t.length() - 1;

        while(i>=0 || j>=0) {
            if ((i >= 0 && s.charAt(i) == '#' || j >= 0 && t.charAt(i) == '#'))
            {
                if (i >= 0 && s.charAt(i) == '#')
                {
                    int backCount = 2;
                    while(backCount > 0)
                    {
                        i--;
                        backCount--;
                        if (i >= 0 && s.charAt(i) == '#')
                        {
                            backCount += 2;
                        }
                    }
                }
                if (j >= 0 && s.charAt(j) == '#')
                {
                    int backCount = 2;
                    while(backCount > 0)
                    {
                        j--;
                        backCount--;
                        if (j >= 0 && t.charAt(j) == '#')
                        {
                            backCount += 2;
                        }
                    }
                }
            }
            else 
            {
                if (i < 0 || j < 0) {
                    return false;
                }
                if (s.charAt(i) != t.charAt(j)) {
                    return false;
                } else {
                    i--;
                    j--;
                }
            }

        }
        return true;
    }

    public static void main(String[] args) {
        String s = "ac#d";
        String t = "az#d";

        if (backspaceCompare(s, t)) {
            System.out.println("True");
        } else {
            System.out.println("False");
        }
    }
    
}

Let’s take a closer look at each code and see how things work out.

-1 means that the loops will start from the very end of the stings.

int i = s.length() - 1;
int j = t.length() - 1;

This line checks if both strings at least have 1 or more alphanumeric characters.

while(i>=0 || j>=0)

This line starts an action if both strings have at least 1 or more characters and hit #.

if ((i >= 0 && s.charAt(i) == '#' || j >= 0 && t.charAt(i) == '#'))

This block of code is for the pointer i(the string s).

If the pointer hits #, it will substitute 2 to backCount.

While backCount is not consumed to 0 (or backCount is bigger than 0), it will iterate through the strings, consuming (decrimenting) the backCount .

And again, if it hist another #, backCount will incremented by 2.

if (i >= 0 && s.charAt(i) == '#')
                {
                    int backCount = 2;
                    while(backCount > 0)
                    {
                        i--;
                        backCount--;
                        if (i >= 0 && s.charAt(i) == '#')
                        {
                            backCount += 2;
                        }
                    }
                }

And do the same thing for j.

if (j >= 0 && s.charAt(j) == '#')
                {
                    int backCount = 2;
                    while(backCount > 0)
                    {
                        j--;
                        backCount--;
                        if (j >= 0 && t.charAt(j) == '#')
                        {
                            backCount += 2;
                        }
                    }
                }

And while iterating through the two strings, if both i and j are smaller than 0, it will return false.

Also, if any of the alphanumeric characters don’t match, it will again return false.

else 
            {
                if (i < 0 || j < 0) {
                    return false;
                }
                if (s.charAt(i) != t.charAt(j)) {
                    return false;
                } 

Otherwise, it will keep iterating through both strings until the end.

} else {
        i--;
        j--;
}

Here’s the executed result:

$ java TypedOutStringOS
True