# Check If Word Is Valid After Substitutions
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/check-if-word-is-valid-after-substitutions)
Canonical: https://scaleengineer.com/dsa/problems/check-if-word-is-valid-after-substitutions
**Data structures:** String, Stack
**Companies:** [Nutanix](https://scaleengineer.com/companies/nutanix)
---
## Problem
Given a string `s`, determine if it is **valid**.

A string `s` is **valid** if, starting with an empty string `t = ""`, you can **transform** `t` **into** `s` after performing the following operation **any number of times**:

* Insert string `"abc"` into any position in `t`. More formally, `t` becomes `tleft + "abc" + tright`, where `t == tleft + tright`. Note that `tleft` and `tright` may be **empty**.

Return `true` _if_ `s` _is a **valid** string, otherwise, return_ `false`.

**Example 1:**

**Input:** s = "aabcbc"
**Output:** true
**Explanation:**
"" -> "abc" -> "aabcbc"
Thus, "aabcbc" is valid.

**Example 2:**

**Input:** s = "abcabcababcc"
**Output:** true
**Explanation:**
"" -> "abc" -> "abcabc" -> "abcabcabc" -> "abcabcababcc"
Thus, "abcabcababcc" is valid.

**Example 3:**

**Input:** s = "abccba"
**Output:** false
**Explanation:** It is impossible to get "abccba" using the operation.

**Constraints:**

* `1 <= s.length <= 2 * 104`
* `s` consists of letters `'a'`, `'b'`, and `'c'`

# Approaches
## Naive Iterative Replacement
This approach attempts to simulate the reverse of the string formation process. The core idea is that if a string `s` is valid, it must be reducible to an empty string by repeatedly removing occurrences of `"abc"`. The algorithm naively finds and removes `"abc"` substrings in a loop.
**Time:** O(N^2). In each iteration of the loop, `s.contains()` or `s.indexOf()` takes O(N) time, and string replacement also takes O(N) time. Since up to N/3 replacements can occur, the total time complexity is quadratic. · **Space:** O(N), where N is the length of the string. In Java, strings are immutable, so each `replaceFirst` operation creates a new string, requiring space proportional to the current string's length.
**Pros:** Very simple to conceptualize and write.
**Cons:** This approach is fundamentally flawed and will fail for certain valid inputs (e.g., `"abcabcababcc"`). It fails to identify the correct `"abc"` sequence to remove when multiple exist.; The time complexity is very high due to repeated string searching and manipulation, making it impractical for the given constraints.
### Explanation
The algorithm repeatedly scans the string for the substring `"abc"` and removes it. For example, if `s = "aabcbc"`, removing the `"abc"` at index 1 results in `"abc"`. In the next iteration, this remaining `"abc"` is removed, resulting in an empty string, and the function correctly returns `true`.

However, this simple strategy is incorrect because the order of removal matters. Removing the first available `"abc"` might lead to a state where no more `"abc"`s can be formed, even if another removal order would have succeeded. For instance, with `s = "abcabcababcc"`, removing the first `"abc"` yields `"abcababcc"`, which then becomes `"ababcc"`, at which point the process gets stuck and incorrectly returns `false`. A valid string can always be reduced by removing an "innermost" `abc` sequence, which this naive approach fails to identify.

```java
class Solution {
    public boolean isValid(String s) {
        // This is a naive and incorrect approach for some cases.
        while (s.contains("abc")) {
            s = s.replaceFirst("abc", "");
        }
        return s.isEmpty();
    }
}
```
### Algorithm
- Start a loop that continues as long as the string `s` contains the substring `"abc"`.
- Inside the loop, find an occurrence of `"abc"` and replace it with an empty string.
- Repeat this process until no more `"abc"` substrings can be found.
- After the loop terminates, check if the resulting string is empty. If it is, the original string was valid; otherwise, it was not.

## Stack-based Processing
A more robust and efficient approach uses a stack to correctly handle the nested structure of `"abc"` insertions. This method views the problem as one of matching sequences. The characters 'a' and 'b' are treated as opening elements, and 'c' is a closing element that must match a preceding `"ab"` sequence. The Last-In, First-Out (LIFO) nature of a stack is perfect for this.
**Time:** O(N), where N is the length of the string. We perform a single pass over the string, and each stack operation (push, pop, size) takes constant time on average. · **Space:** O(N), where N is the length of the string. In the worst-case scenario (e.g., a string like `"ababab..."`), the stack might need to store all N characters.
**Pros:** Correctly handles all valid and invalid cases.; Efficient linear time complexity, which passes the given constraints.
**Cons:** Uses O(N) extra space for the stack.; The `java.util.Stack` or `ArrayDeque` classes might have some performance overhead compared to a raw array implementation.
### Explanation
We iterate through the input string `s` character by character. A stack is used to store characters that are part of a potential `"abc"` sequence but are not yet complete. When we encounter an 'a' or a 'b', we push it onto the stack. When we see a 'c', we know it must be the end of an `"abc"`. We then check if the stack's top two elements are 'b' and 'a'. If they are, we pop them, effectively removing the `"abc"` sequence. If at any point a 'c' is encountered and the stack's top elements do not form `"ab"`, the string is invalid. After processing the whole string, a valid string would have all its `"abc"` sequences resolved, leaving an empty stack.

```java
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public boolean isValid(String s) {
        // ArrayDeque is generally preferred over Stack in modern Java
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == 'a' || c == 'b') {
                stack.push(c);
            } else { // c == 'c'
                if (stack.size() < 2) {
                    return false;
                }
                char second = stack.pop();
                char first = stack.pop();
                if (second != 'b' || first != 'a') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}
```
### Algorithm
- Initialize an empty stack (a `Deque` is preferred in Java).
- Iterate through each character `c` of the input string `s`.
- If `c` is 'a' or 'b', push it onto the stack.
- If `c` is 'c', it must complete an `"abc"` sequence. Check if the stack contains at least two elements and if the top two elements are 'b' and 'a' respectively.
- If the check is successful, pop both 'b' and 'a' from the stack. This simulates the removal of an `"abc"` subsequence.
- If the check fails, the string is invalid, so return `false` immediately.
- After iterating through the entire string, it is valid if and only if the stack is empty.

## Optimized Array-based Stack (Two Pointers)
This approach is a performance optimization of the stack-based method. Instead of using the `java.util.Stack` or `Deque` class, we simulate a stack using a character array and an integer pointer. This technique, often called the two-pointer method (a read pointer for the input and a write pointer for the stack), avoids the overhead of collection classes and can improve performance due to better memory locality.
**Time:** O(N). A single pass is made through the string, with constant time operations at each step. · **Space:** O(N). Although it's an in-place simulation, a new character array of size N is required in Java. The space complexity is asymptotically the same as the `Deque` approach but with a smaller constant factor.
**Pros:** The most performant solution in practice due to direct array access and no overhead from collection classes.; Correctly solves the problem with optimal time complexity.
**Cons:** Still requires O(N) space in Java because strings are immutable and a new character array must be allocated. In languages like C++ with mutable strings, this could be an O(1) space solution.
### Explanation
The core logic remains the same as the standard stack approach, but the implementation is more direct. We use an integer `i` as a write pointer for a character array, which acts as our stack. We iterate through the input string with a read pointer (implicit in the for-each loop). For 'a' and 'b', we add them to our character array at index `i` and increment `i`. For 'c', we check the elements at `i-1` and `i-2` and, if they match `"ab"`, we simply move `i` back by two, effectively erasing them. This avoids the method call overhead and potential boxing/unboxing associated with Java's collection-based stacks, making it the most efficient solution.

```java
class Solution {
    public boolean isValid(String s) {
        if (s.length() % 3 != 0) {
            return false;
        }
        char[] stack = new char[s.length()];
        int i = 0; // Represents the size of the stack
        for (char c : s.toCharArray()) {
            if (c == 'a' || c == 'b') {
                stack[i++] = c;
            } else { // c == 'c'
                if (i < 2 || stack[i - 1] != 'b' || stack[i - 2] != 'a') {
                    return false;
                }
                i -= 2; // Pop 'b' and 'a'
            }
        }
        return i == 0;
    }
}
```
### Algorithm
- First, perform a quick check: if the length of `s` is not divisible by 3, it cannot be valid, so return `false`.
- Initialize a character array `stack` with the same length as `s`.
- Initialize a pointer `i = 0`, which will represent the top of our simulated stack.
- Iterate through each character `c` of the input string `s`.
- If `c` is 'a' or 'b', push it onto the array-stack: `stack[i++] = c`.
- If `c` is 'c', check if the stack has at least two elements (`i >= 2`) and if the last two elements are 'b' and 'a' (`stack[i-1] == 'b'` and `stack[i-2] == 'a'`).
- If they are, pop the two elements by decrementing the stack pointer: `i -= 2`.
- If the conditions for 'c' are not met, the string is invalid, so return `false`.
- After the loop, the string is valid if and only if the stack is empty, i.e., `i == 0`.

# Solutions
### Java

```java
class Solution {
public
  boolean isValid(String s) {
    if (s.length() % 3 > 0) {
      return false;
    }
    StringBuilder t = new StringBuilder();
    for (char c : s.toCharArray()) {
      t.append(c);
      if (t.length() >= 3 && "abc".equals(t.substring(t.length() - 3))) {
        t.delete(t.length() - 3, t.length());
      }
    }
    return t.isEmpty();
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool isValid(string s) {
    if (s.size() % 3) {
      return false;
    }
    string t;
    for (char c : s) {
      t.push_back(c);
      if (t.size() >= 3 && t.substr(t.size() - 3, 3) == "abc") {
        t.erase(t.end() - 3, t.end());
      }
    }
    return t.empty();
  }
};

```

### Python

```python
class Solution:
    def isValid(self, s: str) -> bool: if len(s) % 3: return False t = [] for c in s: t . append(c) if '' . join(t[- 3:]) == 'abc': t[- 3:] = [] return not t

```