# Solving Leetcode Interviews in Seconds with AI: Maximum Score From Removing Substrings


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "1717" 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
	> You are given a string s and two integers x and y. You can perform two types of operations any number of times.  Remove substring "ab" and gain x points.  	 For example, when removing "ab" from "cabxbae" it becomes "cxbae".   Remove substring "ba" and gain y points. 	 For example, when removing "ba" from "cabxbae" it becomes "cabxe".    Return the maximum points you can gain after applying the above operations on s.   Example 1:  Input: s = "cdbcbbaaabab", x = 4, y = 5 Output: 19 Explanation: - Remove the "ba" underlined in "cdbcbbaaabab". Now, s = "cdbcbbaaab" and 5 points are added to the score. - Remove the "ab" underlined in "cdbcbbaaab". Now, s = "cdbcbbaa" and 4 points are added to the score. - Remove the "ba" underlined in "cdbcbbaa". Now, s = "cdbcba" and 5 points are added to the score. - Remove the "ba" underlined in "cdbcba". Now, s = "cdbc" and 5 points are added to the score. Total score = 5 + 4 + 5 + 5 = 19. Example 2:  Input: s = "aabbaaxybbaabb", x = 5, y = 4 Output: 20    Constraints:  1 <= s.length <= 105 1 <= x, y <= 104 s consists of lowercase English letters.  

	# Explanation
	Here's a breakdown of the solution:

*   **Prioritization:** The core idea is to prioritize removing the substring that yields the most points (either "ab" or "ba") first.
*   **Stack-based Processing:** Use stacks to efficiently identify and remove occurrences of "ab" and "ba" while keeping track of potential removals.
*   **Iterative Optimization:** Iteratively process the string, removing the more valuable substring until no more removals are possible, then move on to removing the less valuable substring.

*   **Runtime Complexity:** O(n), where n is the length of the string.
*   **Storage Complexity:** O(n) in the worst case, due to the stacks.

	
	# Code
	```python
	def max_points(s: str, x: int, y: int) -> int:
    """
    Calculates the maximum points achievable by removing "ab" and "ba" substrings.
    """

    score = 0
    if x > y:
        pattern1, pattern2 = "ab", "ba"
        score1, score2 = x, y
    else:
        pattern1, pattern2 = "ba", "ab"
        score1, score2 = y, x

    stack = []
    for char in s:
        stack.append(char)
        while len(stack) >= 2:
            top = stack[-1]
            second_top = stack[-2]
            if second_top + top == pattern1:
                score += score1
                stack.pop()
                stack.pop()
            else:
                break
    
    temp_string = "".join(stack)
    stack = []

    for char in temp_string:
        stack.append(char)
        while len(stack) >= 2:
            top = stack[-1]
            second_top = stack[-2]
            if second_top + top == pattern2:
                score += score2
                stack.pop()
                stack.pop()
            else:
                break

    return score
	```