# Solving Leetcode Interviews in Seconds with AI: Check If Word Is Valid After Substitutions


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "1003" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> 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'  

	# Explanation
	Here's an efficient approach to solve the string validity problem:

*   **Stack-based Validation:** Use a stack to simulate the building of the string `s` by inserting "abc" at different locations.
*   **Matching 'c' with 'b' and 'a':** When encountering a 'c', check if the stack has 'b' and 'a' on top (in that order). If so, pop 'b' and 'a'. This simulates removing "abc".
*   **Final Check:** After processing the entire string, the stack should be empty. If it's empty, the string is valid; otherwise, it's invalid.

*   **Runtime Complexity:** O(n), where n is the length of the string `s`. **Storage Complexity:** O(n) in the worst-case scenario (e.g., "aaaa...a").

	
	# Code
	```python
	def isValid(s: str) -> bool:
    stack = []
    for char in s:
        if char == 'c':
            if len(stack) >= 2 and stack[-1] == 'b' and stack[-2] == 'a':
                stack.pop()
                stack.pop()
            else:
                return False
        else:
            stack.append(char)
    return len(stack) == 0
	```