Check If Word Is Valid After Substitutions
MedPrompt
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 int. More formally,tbecomestleft + "abc" + tright, wheret == tleft + tright. Note thattleftandtrightmay 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 * 104sconsists of letters'a','b', and'c'
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Start a loop that continues as long as the string
scontains 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.
Walkthrough
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.
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(); }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Initialize an empty stack (a
Dequeis preferred in Java). - Iterate through each character
cof the input strings. - If
cis 'a' or 'b', push it onto the stack. - If
cis '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
falseimmediately. - After iterating through the entire string, it is valid if and only if the stack is empty.
Walkthrough
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.
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(); }}Complexity
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.
Trade-offs
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.StackorArrayDequeclasses might have some performance overhead compared to a raw array implementation.
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.
Algorithm
- First, perform a quick check: if the length of
sis not divisible by 3, it cannot be valid, so returnfalse. - Initialize a character array
stackwith the same length ass. - Initialize a pointer
i = 0, which will represent the top of our simulated stack. - Iterate through each character
cof the input strings. - If
cis 'a' or 'b', push it onto the array-stack:stack[i++] = c. - If
cis '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'andstack[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.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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(); }}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(); }};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 tVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.