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.
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(); }}Video 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.