LeetCode 1003: Check If Word Is Valid After Substitutions Solution

Master LeetCode problem 1003 (Check If Word Is Valid After Substitutions), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1003. Check If Word Is Valid After Substitutions

Medium

String Stack

Problem Explanation

Explanation:

To solve this problem, we can iterate through the input string s and keep checking if we can find the pattern "abc" in it. If we find "abc", we remove it from the string and continue with the next iteration. If at the end, the string becomes empty, then it is a valid string, otherwise it is invalid.

We can use a stack to keep track of the characters encountered.
If we find 'a', 'b', 'c' consecutively in the input string, we pop 'a' and 'b' from the stack and continue.
If we reach the end of the input string and the stack is empty, the string is valid.

Time complexity: O(n) Space complexity: O(n)

Solution Code

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        
        for (char c : s.toCharArray()) {
            if (c == 'c') {
                if (stack.isEmpty() || stack.pop() != 'b') return false;
                if (stack.isEmpty() || stack.pop() != 'a') return false;
            } else {
                stack.push(c);
            }
        }
        
        return stack.isEmpty();
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1003 (Check If Word Is Valid After Substitutions)?

This page provides optimized solutions for LeetCode problem 1003 (Check If Word Is Valid After Substitutions) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1003 (Check If Word Is Valid After Substitutions)?

The time complexity for LeetCode 1003 (Check If Word Is Valid After Substitutions) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1003 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1003 in Java, C++, or Python.

Back to LeetCode Solutions