🔗 Removing Pairs

Removing pairs starts with a string made up of lowercase alphabet letters. First, find a pair of the same alphabet letter placed next to each other in the string. Then, remove both of them and join the remaining parts of the string together. Repeat this process, and if you're able to remove the entire string, the pair-removal process is considered complete. Given a string S, complete a function that returns whether the pair-removal process can be successfully carried out. Return 1 if it can succeed, and 0 if it can't.

For example, for the string S = baabaa

b aa baa → bb aa → aa →

By following this order, the entire string can be removed, so it returns 1.

• String length: a natural number up to 1,000,000
• The string consists entirely of lowercase letters.

Input/Output Example #1

Same as the example above.

Input/Output Example #2

Even though characters still remain in the string, there's no more removable pair, so it returns 0.

At first, I approached it with a while loop and the charAt method, and it worked, but it was way too slow.

After thinking about it for a while, I realized it was very similar to Level 1's Crane Doll Picking Game (64061).

That problem involves an operation where a doll is removed if the same doll is picked consecutively.

If you think of that problem's dolls as characters instead, you can see they're very similar.

Push characters one by one into a Stack, and before pushing, pop and compare the most recently inserted element.

If they match, it means the same character appeared twice in a row, so remove the last element from the stack without inserting.

If not, simply insert it.

Example: baabaa

1. Since the stack is empty, insert b.
2. Compare the next character a with the stack's most recent element b.
   1. Since they're not equal, insert a.
3. Compare the next character a with the stack's most recent element a.
   1. Since they're equal, remove the stack's most recent element a.
4. Compare the next character b with the stack's most recent element b.
   1. Since they're equal, remove the stack's most recent element b.
5. Since the stack is empty, insert the next character a.
6. Compare the next character a with the stack's most recent element a.
   1. Since they're equal, remove the stack's most recent element a.
7. If the stack is empty, return 1; otherwise, return 0.

Since it's limited to two consecutive matching characters, there's no need to consider three or more consecutive matching characters.

JAVA
import java.util.Stack;

/**
 * Removing Pairs class
 *
 * @author RWB
 * @since 2021.12.28 Tue 17:38:51
 */
class Solution
{
	/**
	 * Answer return method
	 *
	 * @param s: [String] String
	 *
	 * @return [int] Answer
	 */
	public int solution(String s)
	{
		Stack<Character> stack = new Stack<>();
		
		for (char c : s.toCharArray())
		{
			// If the stack is empty
			if (stack.isEmpty())
			{
				stack.add(c);
			}
			
			// If not
			else
			{
				// If the characters are adjacent
				if (c == stack.peek())
				{
					stack.pop();
				}
				
				// If not
				else
				{
					stack.add(c);
				}
			}
		}
		
		return stack.isEmpty() ? 1 : 0;
	}
}