Check If Word Is Valid After Substitutions

Medium
379.

Check If Word Is Valid After Substitutions

Check If Word Is Valid After Substitutions is a medium coding problem on strings and stack, asked in Amazon, Google and Nutanix interviews.

A string is valid if it can be built from the empty string by repeatedly inserting "abc" at any position.

Given a string s, return true if it is valid.

Example 1

Input
s = "aabcbc"
Output
true
Explanation
Insert "abc" into "abc" after the first a.

Example 2

Input
s = "abcabcababcc"
Output
true

Example 3

Input
s = "abccba"
Output
false

Constraints

  • 1 <= s.length <= 40
  • s consists of the letters 'a', 'b' and 'c'.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Check If Word Is Valid After Substitutions — Solution

Check If Word Is Valid After Substitutions solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Check If Word Is Valid After Substitutions is a medium coding problem on strings and stack, asked in Amazon, Google and Nutanix interviews.

  • Difficulty: Medium
  • Topics: Strings, Stack
  • Asked at: Amazon, Google, Nutanix
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A string is valid if it can be built from the empty string by repeatedly inserting "abc" at any position.

Given a string s, return true if it is valid.

Example 1

Input: s = "aabcbc"
Output: true
Explanation: Insert "abc" into "abc" after the first a.

Example 2

Input: s = "abcabcababcc"
Output: true

Example 3

Input: s = "abccba"
Output: false

Constraints

  • 1 <= s.length <= 40
  • s consists of the letters 'a', 'b' and 'c'.

Hints for Check If Word Is Valid After Substitutions

  1. Hint 1

    Every insertion places abc contiguously, so the string always contains an abc you can delete.

  2. Hint 2

    Push characters on a stack; when you see a c, the two items below it must be a then b.

  3. Hint 3

    If that check ever fails, or anything is left on the stack at the end, the string is invalid.

How to solve Check If Word Is Valid After Substitutions

Every insertion places abc contiguously, so a valid string always contains an abc to delete. Push characters; on c, the top two must be a, b.

Approach

  1. For a or b, push.
  2. For c, pop two and require them to be b then a; fail otherwise.
  3. Return whether the stack is empty.

Why it works

Reversing the insertion process by repeatedly deleting abc works in any order, and the stack finds the leftmost-completed one each time.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • A length not divisible by 3 can be rejected immediately.

Reference solution

Python

def isValid(s: str) -> bool:
    stack = []
    for ch in s:
        if ch == "c":
            if len(stack) < 2:
                return False
            b = stack.pop()
            a = stack.pop()
            if a != "a" or b != "b":
                return False
        else:
            stack.append(ch)
    return len(stack) == 0

Java

public static boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == 'c') {
            if (stack.size() < 2) return false;
            char b = stack.pop();
            char a = stack.pop();
            if (a != 'a' || b != 'b') return false;
        } else {
            stack.push(c);
        }
    }
    return stack.isEmpty();
}

C++

bool isValid(string s) {
    vector<char> stack;
    for (char c : s) {
        if (c == 'c') {
            if (stack.size() < 2) return false;
            char b = stack.back();
            stack.pop_back();
            char a = stack.back();
            stack.pop_back();
            if (a != 'a' || b != 'b') return false;
        } else {
            stack.push_back(c);
        }
    }
    return stack.empty();
}

JavaScript

var isValid = function(s) {
    const stack = [];
    for (let i = 0; i < s.length; i++) {
        const c = s.charAt(i);
        if (c === "c") {
            if (stack.length < 2) return false;
            const b = stack.pop();
            const a = stack.pop();
            if (a !== "a" || b !== "b") return false;
        } else {
            stack.push(c);
        }
    }
    return stack.length === 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Stack Data Structure