Zuma Game (Min Moves to Clear)

🎯

Zuma Game (Min Moves to Clear)

hardDPAmazonGoogle

Imagine a colorful chain of balls on a table, and you want to clear them all by inserting the fewest possible balls to trigger chain reactions.

💡 This problem is a classic example of interval dynamic programming combined with game-like state transitions. Beginners often struggle because it requires thinking about how inserting balls affects future states and how to optimally split intervals.

📋

Problem Statement

You are given a string representing a row of colored balls on a table and another string representing your hand of balls. Each ball is represented by a character. Your goal is to clear all the balls on the table by inserting balls from your hand into the row. When three or more consecutive balls of the same color appear, they are removed, and this removal may trigger further removals recursively. Return the minimum number of balls you need to insert to clear the table. If it is impossible, return -1.

1 ≤ length of board ≤ 161 ≤ length of hand ≤ 5board and hand consist only of characters 'R', 'Y', 'B', 'G', 'W'

💡

Example

Input"board = \"WRRBBW\", hand = \"RB\""

Output-1

No matter how you insert balls from hand, you cannot clear the board.

Input"board = \"WWRRBBWW\", hand = \"WRBRW\""

Output2

Insert 'R' at position 2 and 'B' at position 5 to clear the board.

• Empty board initially → 0 moves needed
• Hand has no balls → impossible to clear if board not empty
• Board with all balls same color → may clear with minimal insertions
• Board with alternating colors and hand missing needed colors → impossible

🔁

Why DP?

Why greedy fails:

Greedy fails because inserting balls to clear one group may prevent clearing another group later. For example, clearing a small group first may block a larger chain reaction that would clear more balls with fewer insertions.

DP state:

dp[i][j][hand_state] represents the minimum number of balls needed to clear the substring board[i..j] given the current hand state.

Recurrence:dp[i][j][hand] = min over k in [i,j) of dp[i][k][hand'] + dp[k+1][j][hand''] where hand', hand'' are updated hand states after removals

The minimal moves to clear an interval is the minimum over splitting it into two parts and clearing each, considering how hand balls are used and removals cascade.

⚠️

Common Mistakes

Not removing consecutive balls recursively after insertion

Incorrect board state leads to wrong minimal moves

✅ Implement recursive removal until no groups ≥3 remain

Not memoizing states properly (e.g., ignoring hand counts)

Exponential time due to repeated computations

✅ Include both board and hand state in memo keys

Using greedy insertion without exploring all positions

Suboptimal moves and wrong answers

✅ Try inserting balls at every possible position

Incorrectly calculating balls needed to remove groups

Over or under counting insertions, wrong minimal moves

✅ Calculate balls needed as max(0, 3 - group size)

🧠

Brute Force (Pure Recursion with Backtracking)

💡 This approach explores all possible insertions and removals without caching results. It is the foundation to understand the problem's complexity and why optimization is necessary.

Intuition

Try inserting each ball from the hand into every possible position on the board, then remove consecutive balls recursively. Repeat until the board is empty or no moves remain.

Algorithm

1. If the board is empty, return 0 moves needed.
2. For each position in the board, try inserting each ball from the hand.
3. After insertion, remove consecutive balls recursively.
4. Recurse on the new board and updated hand to find minimal moves.

💡 The recursion and removal steps are tricky because removals cascade and the state space grows exponentially.

Recurrence:f(board, hand) = min over all insertions { 1 + f(new_board_after_removal, new_hand) }

</>

Code

from collections import Counter

def findMinStep(board: str, hand: str) -> int:
    hand_count = Counter(hand)

    def remove_consecutive(s):
        i = 0
        while i < len(s):
            j = i
            while j < len(s) and s[j] == s[i]:
                j += 1
            if j - i >= 3:
                s = s[:i] + s[j:]
                i = 0
            else:
                i += 1
        return s

    memo = {}

    def dfs(s, hand_count):
        if not s:
            return 0
        key = (s, tuple(sorted(hand_count.items())))
        if key in memo:
            return memo[key]
        res = float('inf')
        for i in range(len(s) + 1):
            for c in hand_count:
                if hand_count[c] == 0:
                    continue
                new_s = s[:i] + c + s[i:]
                new_s = remove_consecutive(new_s)
                hand_count[c] -= 1
                temp = dfs(new_s, hand_count)
                if temp != -1:
                    res = min(res, 1 + temp)
                hand_count[c] += 1
        memo[key] = -1 if res == float('inf') else res
        return memo[key]

    return dfs(board, hand_count)

# Example usage:
if __name__ == '__main__':
    print(findMinStep("WRRBBW", "RB"))  # Output: -1
    print(findMinStep("WWRRBBWW", "WRBRW"))  # Output: 2

Line Notes

hand_count = Counter(hand)Count balls in hand to track availability efficiently

def remove_consecutive(s):Helper to remove consecutive balls recursively

while j < len(s) and s[j] == s[i]:Find consecutive balls of the same color

if j - i >= 3:Remove group if size >= 3 to trigger chain reaction

key = (s, tuple(sorted(hand_count.items())))Memoization key to avoid recomputation of same state

for i in range(len(s) + 1):Try inserting ball at every possible position

for c in hand_count:Try every ball color available in hand

hand_count[c] -= 1Use one ball of color c from hand

memo[key] = -1 if res == float('inf') else resStore result or -1 if no solution

import java.util.*;

public class ZumaGame {
    private Map<String, Integer> memo = new HashMap<>();

    public int findMinStep(String board, String hand) {
        int[] handCount = new int[26];
        for (char c : hand.toCharArray()) handCount[c - 'A']++;
        int res = dfs(board, handCount);
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    private int dfs(String board, int[] handCount) {
        if (board.length() == 0) return 0;
        String key = board + Arrays.toString(handCount);
        if (memo.containsKey(key)) return memo.get(key);
        int res = Integer.MAX_VALUE;
        for (int i = 0; i <= board.length(); i++) {
            for (int c = 0; c < 26; c++) {
                if (handCount[c] == 0) continue;
                char ch = (char) (c + 'A');
                String newBoard = removeConsecutive(board.substring(0, i) + ch + board.substring(i));
                handCount[c]--;
                int temp = dfs(newBoard, handCount);
                if (temp != Integer.MAX_VALUE) res = Math.min(res, 1 + temp);
                handCount[c]++;
            }
        }
        memo.put(key, res);
        return res;
    }

    private String removeConsecutive(String s) {
        int i = 0;
        while (i < s.length()) {
            int j = i;
            while (j < s.length() && s.charAt(j) == s.charAt(i)) j++;
            if (j - i >= 3) {
                s = s.substring(0, i) + s.substring(j);
                i = 0;
            } else {
                i++;
            }
        }
        return s;
    }

    public static void main(String[] args) {
        ZumaGame zg = new ZumaGame();
        System.out.println(zg.findMinStep("WRRBBW", "RB")); // -1
        System.out.println(zg.findMinStep("WWRRBBWW", "WRBRW")); // 2
    }
}

Line Notes

private Map<String, Integer> memo = new HashMap<>();Memoize results to avoid recomputation

int[] handCount = new int[26];Count balls in hand by character index

for (int i = 0; i <= board.length(); i++) {Try inserting at every position

if (handCount[c] == 0) continue;Skip colors not available in hand

String newBoard = removeConsecutive(...)Remove consecutive balls after insertion

memo.put(key, res);Store computed result for current state

#include <bits/stdc++.h>
using namespace std;

class Solution {
    unordered_map<string, int> memo;

    string removeConsecutive(string s) {
        int i = 0;
        while (i < (int)s.size()) {
            int j = i;
            while (j < (int)s.size() && s[j] == s[i]) j++;
            if (j - i >= 3) {
                s = s.substr(0, i) + s.substr(j);
                i = 0;
            } else {
                i++;
            }
        }
        return s;
    }

    int dfs(string board, vector<int>& handCount) {
        if (board.empty()) return 0;
        string key = board + "#";
        for (int c : handCount) key += to_string(c) + ",";
        if (memo.count(key)) return memo[key];
        int res = INT_MAX;
        for (int i = 0; i <= (int)board.size(); i++) {
            for (int c = 0; c < 26; c++) {
                if (handCount[c] == 0) continue;
                char ch = 'A' + c;
                string newBoard = board.substr(0, i) + ch + board.substr(i);
                newBoard = removeConsecutive(newBoard);
                handCount[c]--;
                int temp = dfs(newBoard, handCount);
                if (temp != INT_MAX) res = min(res, 1 + temp);
                handCount[c]++;
            }
        }
        return memo[key] = res;
    }

public:
    int findMinStep(string board, string hand) {
        vector<int> handCount(26, 0);
        for (char c : hand) handCount[c - 'A']++;
        int res = dfs(board, handCount);
        return res == INT_MAX ? -1 : res;
    }
};

int main() {
    Solution sol;
    cout << sol.findMinStep("WRRBBW", "RB") << "\n"; // -1
    cout << sol.findMinStep("WWRRBBWW", "WRBRW") << "\n"; // 2
    return 0;
}

Line Notes

unordered_map<string, int> memo;Memoize states to prune recursion

while (j < (int)s.size() && s[j] == s[i]) j++;Find consecutive balls for removal

string key = board + "#";Create unique key for memo including hand counts

for (int c = 0; c < 26; c++) {Try all ball colors in hand

handCount[c]--Use one ball of color c

return memo[key] = res;Cache and return minimal moves

var findMinStep = function(board, hand) {
    const handCount = {};
    for (const c of hand) handCount[c] = (handCount[c] || 0) + 1;

    function removeConsecutive(s) {
        let i = 0;
        while (i < s.length) {
            let j = i;
            while (j < s.length && s[j] === s[i]) j++;
            if (j - i >= 3) {
                s = s.slice(0, i) + s.slice(j);
                i = 0;
            } else {
                i++;
            }
        }
        return s;
    }

    const memo = new Map();

    function dfs(s, handCount) {
        if (s.length === 0) return 0;
        const key = s + JSON.stringify(handCount);
        if (memo.has(key)) return memo.get(key);
        let res = Infinity;
        for (let i = 0; i <= s.length; i++) {
            for (const c in handCount) {
                if (handCount[c] === 0) continue;
                const newS = removeConsecutive(s.slice(0, i) + c + s.slice(i));
                handCount[c]--;
                const temp = dfs(newS, handCount);
                if (temp !== -1) res = Math.min(res, 1 + temp);
                handCount[c]++;
            }
        }
        memo.set(key, res === Infinity ? -1 : res);
        return memo.get(key);
    }

    return dfs(board, handCount);
};

// Example usage:
console.log(findMinStep("WRRBBW", "RB")); // -1
console.log(findMinStep("WWRRBBWW", "WRBRW")); // 2

Line Notes

const handCount = {};Count balls in hand for quick lookup

function removeConsecutive(s)Remove consecutive balls recursively

const key = s + JSON.stringify(handCount);Memo key combines board and hand state

for (let i = 0; i <= s.length; i++) {Try inserting at every position

handCount[c]--Use one ball of color c

memo.set(key, res === Infinity ? -1 : res);Cache result or -1 if no solution

⏱

Complexity

TimeO((n + m) * 5^(n+m)) where n = board length, m = hand length

SpaceO((n + m) * 5^(n+m)) due to memoization and recursion stack

Each recursive call tries all insertions and colors, leading to exponential states

💡 For n=10 and m=5, this is roughly millions of calls, which is impractical without pruning.

Interview Verdict: TLE / Use only to introduce problem and motivate memoization

Shows why naive recursion is infeasible and sets stage for DP optimization.

🧠

Memoized Recursion (Top-Down DP with State Compression)

💡 This approach adds memoization to the brute force recursion to avoid recomputing states, drastically improving performance.

Intuition

Cache results of subproblems identified by board string and hand counts to prune repeated work.

Algorithm

1. Represent hand as a count of balls by color.
2. Use a memo dictionary keyed by (board, hand state) to store results.
3. For each insertion, recursively compute minimal moves on the new board.
4. Return cached results when available to avoid recomputation.

💡 Memoization is the key to making recursion feasible by pruning duplicate states.

Recurrence:dp(board, hand) = min over insertions { 1 + dp(new_board_after_removal, new_hand) } with memoization

</>

Code

from collections import Counter

def findMinStep(board: str, hand: str) -> int:
    hand_count = Counter(hand)

    def remove_consecutive(s):
        i = 0
        while i < len(s):
            j = i
            while j < len(s) and s[j] == s[i]:
                j += 1
            if j - i >= 3:
                s = s[:i] + s[j:]
                i = 0
            else:
                i += 1
        return s

    memo = {}

    def dfs(s, hand_count):
        if not s:
            return 0
        key = (s, tuple(sorted(hand_count.items())))
        if key in memo:
            return memo[key]
        res = float('inf')
        for i in range(len(s) + 1):
            for c in hand_count:
                if hand_count[c] == 0:
                    continue
                new_s = s[:i] + c + s[i:]
                new_s = remove_consecutive(new_s)
                hand_count[c] -= 1
                temp = dfs(new_s, hand_count)
                if temp != -1:
                    res = min(res, 1 + temp)
                hand_count[c] += 1
        memo[key] = -1 if res == float('inf') else res
        return memo[key]

    return dfs(board, hand_count)

# Example usage:
if __name__ == '__main__':
    print(findMinStep("WRRBBW", "RB"))  # Output: -1
    print(findMinStep("WWRRBBWW", "WRBRW"))  # Output: 2

Line Notes

memo = {}Initialize memo dictionary to cache results

key = (s, tuple(sorted(hand_count.items())))Create unique key for memoization

if key in memo:Return cached result if available

hand_count[c] -= 1Use one ball from hand before recursion

memo[key] = -1 if res == float('inf') else resStore computed minimal moves or -1 if impossible

import java.util.*;

public class ZumaGameMemo {
    private Map<String, Integer> memo = new HashMap<>();

    public int findMinStep(String board, String hand) {
        int[] handCount = new int[26];
        for (char c : hand.toCharArray()) handCount[c - 'A']++;
        int res = dfs(board, handCount);
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    private int dfs(String board, int[] handCount) {
        if (board.length() == 0) return 0;
        String key = board + Arrays.toString(handCount);
        if (memo.containsKey(key)) return memo.get(key);
        int res = Integer.MAX_VALUE;
        for (int i = 0; i <= board.length(); i++) {
            for (int c = 0; c < 26; c++) {
                if (handCount[c] == 0) continue;
                char ch = (char) (c + 'A');
                String newBoard = removeConsecutive(board.substring(0, i) + ch + board.substring(i));
                handCount[c]--;
                int temp = dfs(newBoard, handCount);
                if (temp != Integer.MAX_VALUE) res = Math.min(res, 1 + temp);
                handCount[c]++;
            }
        }
        memo.put(key, res);
        return res;
    }

    private String removeConsecutive(String s) {
        int i = 0;
        while (i < s.length()) {
            int j = i;
            while (j < s.length() && s.charAt(j) == s.charAt(i)) j++;
            if (j - i >= 3) {
                s = s.substring(0, i) + s.substring(j);
                i = 0;
            } else {
                i++;
            }
        }
        return s;
    }

    public static void main(String[] args) {
        ZumaGameMemo zg = new ZumaGameMemo();
        System.out.println(zg.findMinStep("WRRBBW", "RB")); // -1
        System.out.println(zg.findMinStep("WWRRBBWW", "WRBRW")); // 2
    }
}

Line Notes

private Map<String, Integer> memo = new HashMap<>();Memoize results to avoid repeated computation

String key = board + Arrays.toString(handCount);Unique key for current board and hand state

if (memo.containsKey(key)) return memo.get(key);Return cached result if available

handCount[c]--Use one ball of color c before recursion

memo.put(key, res);Cache the minimal moves for this state

#include <bits/stdc++.h>
using namespace std;

class SolutionMemo {
    unordered_map<string, int> memo;

    string removeConsecutive(string s) {
        int i = 0;
        while (i < (int)s.size()) {
            int j = i;
            while (j < (int)s.size() && s[j] == s[i]) j++;
            if (j - i >= 3) {
                s = s.substr(0, i) + s.substr(j);
                i = 0;
            } else {
                i++;
            }
        }
        return s;
    }

    int dfs(string board, vector<int>& handCount) {
        if (board.empty()) return 0;
        string key = board + "#";
        for (int c : handCount) key += to_string(c) + ",";
        if (memo.count(key)) return memo[key];
        int res = INT_MAX;
        for (int i = 0; i <= (int)board.size(); i++) {
            for (int c = 0; c < 26; c++) {
                if (handCount[c] == 0) continue;
                char ch = 'A' + c;
                string newBoard = board.substr(0, i) + ch + board.substr(i);
                newBoard = removeConsecutive(newBoard);
                handCount[c]--;
                int temp = dfs(newBoard, handCount);
                if (temp != INT_MAX) res = min(res, 1 + temp);
                handCount[c]++;
            }
        }
        return memo[key] = res;
    }

public:
    int findMinStep(string board, string hand) {
        vector<int> handCount(26, 0);
        for (char c : hand) handCount[c - 'A']++;
        int res = dfs(board, handCount);
        return res == INT_MAX ? -1 : res;
    }
};

int main() {
    SolutionMemo sol;
    cout << sol.findMinStep("WRRBBW", "RB") << "\n"; // -1
    cout << sol.findMinStep("WWRRBBWW", "WRBRW") << "\n"; // 2
    return 0;
}

Line Notes

unordered_map<string, int> memo;Cache results to avoid recomputation

string key = board + "#";Create unique key including hand counts

if (memo.count(key)) return memo[key];Return cached result if exists

handCount[c]--Use one ball before recursive call

return memo[key] = res;Store and return minimal moves

var findMinStep = function(board, hand) {
    const handCount = {};
    for (const c of hand) handCount[c] = (handCount[c] || 0) + 1;

    function removeConsecutive(s) {
        let i = 0;
        while (i < s.length) {
            let j = i;
            while (j < s.length && s[j] === s[i]) j++;
            if (j - i >= 3) {
                s = s.slice(0, i) + s.slice(j);
                i = 0;
            } else {
                i++;
            }
        }
        return s;
    }

    const memo = new Map();

    function dfs(s, handCount) {
        if (s.length === 0) return 0;
        const key = s + JSON.stringify(handCount);
        if (memo.has(key)) return memo.get(key);
        let res = Infinity;
        for (let i = 0; i <= s.length; i++) {
            for (const c in handCount) {
                if (handCount[c] === 0) continue;
                const newS = removeConsecutive(s.slice(0, i) + c + s.slice(i));
                handCount[c]--;
                const temp = dfs(newS, handCount);
                if (temp !== -1) res = Math.min(res, 1 + temp);
                handCount[c]++;
            }
        }
        memo.set(key, res === Infinity ? -1 : res);
        return memo.get(key);
    }

    return dfs(board, handCount);
};

// Example usage:
console.log(findMinStep("WRRBBW", "RB")); // -1
console.log(findMinStep("WWRRBBWW", "WRBRW")); // 2

Line Notes

const memo = new Map();Memoize results to prune repeated states

const key = s + JSON.stringify(handCount);Unique key for current board and hand

if (memo.has(key)) return memo.get(key);Return cached result if available

handCount[c]--Use one ball before recursion

memo.set(key, res === Infinity ? -1 : res);Cache minimal moves or -1 if impossible

⏱

Complexity

TimeO(n * m * 5^(n+m)) with memoization pruning many states

SpaceO(n * m * 5^(n+m)) for memo and recursion stack

Memoization reduces repeated work but worst case remains exponential

💡 Memoization makes the problem solvable for typical interview constraints.

Interview Verdict: Accepted with pruning, practical for interview coding

Shows how to optimize brute force with DP techniques.

🧠

Interval DP with Memoization (Optimal Substructure Exploitation)

💡 This approach models the problem as clearing intervals of the board, using DP to combine solutions of subintervals and hand states, achieving optimal performance.

Intuition

Split the board into intervals and compute minimal moves to clear each interval, combining results and using hand balls to trigger removals.

Algorithm

1. Define dp(i, j, hand) as minimal moves to clear substring board[i..j] with current hand.
2. If substring is empty, return 0.
3. Try removing consecutive balls by inserting balls from hand to form groups of 3 or more.
4. Split interval into two parts and combine minimal moves from subintervals.
5. Memoize results to avoid recomputation.

💡 Interval DP requires careful state definition and combining subproblems, which is challenging but powerful.

Recurrence:dp(i,j,hand) = min { dp(i,k,hand') + dp(k+1,j,hand'') } over k in [i,j) and insertions to remove groups

</>

Code

from collections import Counter
import sys
sys.setrecursionlimit(10**7)

def findMinStep(board: str, hand: str) -> int:
    hand_count = Counter(hand)

    def remove_consecutive(s):
        i = 0
        while i < len(s):
            j = i
            while j < len(s) and s[j] == s[i]:
                j += 1
            if j - i >= 3:
                s = s[:i] + s[j:]
                i = 0
            else:
                i += 1
        return s

    memo = {}

    def dp(s, hand_count):
        if not s:
            return 0
        key = (s, tuple(sorted(hand_count.items())))
        if key in memo:
            return memo[key]
        res = float('inf')
        i = 0
        while i < len(s):
            j = i
            while j < len(s) and s[j] == s[i]:
                j += 1
            balls_needed = 3 - (j - i)
            c = s[i]
            if hand_count[c] >= balls_needed:
                hand_count[c] -= balls_needed
                new_s = s[:i] + s[j:]
                new_s = remove_consecutive(new_s)
                temp = dp(new_s, hand_count)
                if temp != -1:
                    res = min(res, balls_needed + temp)
                hand_count[c] += balls_needed
            i = j
        memo[key] = -1 if res == float('inf') else res
        return memo[key]

    return dp(board, hand_count)

# Example usage:
if __name__ == '__main__':
    print(findMinStep("WRRBBW", "RB"))  # Output: -1
    print(findMinStep("WWRRBBWW", "WRBRW"))  # Output: 2

Line Notes

sys.setrecursionlimit(10**7)Increase recursion limit for deep recursion

while j < len(s) and s[j] == s[i]:Find consecutive balls to check groups

balls_needed = 3 - (j - i)Calculate how many balls needed to remove group

if hand_count[c] >= balls_needed:Check if hand has enough balls to remove group

hand_count[c] -= balls_neededUse balls from hand before recursion

new_s = remove_consecutive(new_s)Remove balls recursively after insertion

memo[key] = -1 if res == float('inf') else resCache minimal moves or -1 if impossible

import java.util.*;

public class ZumaGameIntervalDP {
    private Map<String, Integer> memo = new HashMap<>();

    public int findMinStep(String board, String hand) {
        int[] handCount = new int[26];
        for (char c : hand.toCharArray()) handCount[c - 'A']++;
        int res = dp(board, handCount);
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    private int dp(String s, int[] handCount) {
        if (s.length() == 0) return 0;
        String key = s + Arrays.toString(handCount);
        if (memo.containsKey(key)) return memo.get(key);
        int res = Integer.MAX_VALUE;
        int i = 0;
        while (i < s.length()) {
            int j = i;
            while (j < s.length() && s.charAt(j) == s.charAt(i)) j++;
            int ballsNeeded = 3 - (j - i);
            char c = s.charAt(i);
            if (handCount[c - 'A'] >= ballsNeeded) {
                handCount[c - 'A'] -= ballsNeeded;
                String newS = s.substring(0, i) + s.substring(j);
                newS = removeConsecutive(newS);
                int temp = dp(newS, handCount);
                if (temp != Integer.MAX_VALUE) res = Math.min(res, ballsNeeded + temp);
                handCount[c - 'A'] += ballsNeeded;
            }
            i = j;
        }
        memo.put(key, res);
        return res;
    }

    private String removeConsecutive(String s) {
        int i = 0;
        while (i < s.length()) {
            int j = i;
            while (j < s.length() && s.charAt(j) == s.charAt(i)) j++;
            if (j - i >= 3) {
                s = s.substring(0, i) + s.substring(j);
                i = 0;
            } else {
                i++;
            }
        }
        return s;
    }

    public static void main(String[] args) {
        ZumaGameIntervalDP zg = new ZumaGameIntervalDP();
        System.out.println(zg.findMinStep("WRRBBW", "RB")); // -1
        System.out.println(zg.findMinStep("WWRRBBWW", "WRBRW")); // 2
    }
}

Line Notes

int ballsNeeded = 3 - (j - i);Calculate balls needed to remove group

if (handCount[c - 'A'] >= ballsNeeded)Check if hand has enough balls

handCount[c - 'A'] -= ballsNeeded;Use balls before recursion

newS = removeConsecutive(newS);Remove balls recursively after insertion

memo.put(key, res);Cache minimal moves for current state

#include <bits/stdc++.h>
using namespace std;

class SolutionIntervalDP {
    unordered_map<string, int> memo;

    string removeConsecutive(string s) {
        int i = 0;
        while (i < (int)s.size()) {
            int j = i;
            while (j < (int)s.size() && s[j] == s[i]) j++;
            if (j - i >= 3) {
                s = s.substr(0, i) + s.substr(j);
                i = 0;
            } else {
                i++;
            }
        }
        return s;
    }

    int dp(string s, vector<int>& handCount) {
        if (s.empty()) return 0;
        string key = s + "#";
        for (int c : handCount) key += to_string(c) + ",";
        if (memo.count(key)) return memo[key];
        int res = INT_MAX;
        int i = 0;
        while (i < (int)s.size()) {
            int j = i;
            while (j < (int)s.size() && s[j] == s[i]) j++;
            int ballsNeeded = 3 - (j - i);
            char c = s[i];
            if (handCount[c - 'A'] >= ballsNeeded) {
                handCount[c - 'A'] -= ballsNeeded;
                string newS = s.substr(0, i) + s.substr(j);
                newS = removeConsecutive(newS);
                int temp = dp(newS, handCount);
                if (temp != INT_MAX) res = min(res, ballsNeeded + temp);
                handCount[c - 'A'] += ballsNeeded;
            }
            i = j;
        }
        return memo[key] = res;
    }

public:
    int findMinStep(string board, string hand) {
        vector<int> handCount(26, 0);
        for (char c : hand) handCount[c - 'A']++;
        int res = dp(board, handCount);
        return res == INT_MAX ? -1 : res;
    }
};

int main() {
    SolutionIntervalDP sol;
    cout << sol.findMinStep("WRRBBW", "RB") << "\n"; // -1
    cout << sol.findMinStep("WWRRBBWW", "WRBRW") << "\n"; // 2
    return 0;
}

Line Notes

int ballsNeeded = 3 - (j - i);Calculate how many balls needed to remove group

if (handCount[c - 'A'] >= ballsNeeded)Check if hand has enough balls

handCount[c - 'A'] -= ballsNeeded;Use balls before recursion

newS = removeConsecutive(newS);Remove balls recursively after insertion

return memo[key] = res;Cache and return minimal moves

var findMinStep = function(board, hand) {
    const handCount = {};
    for (const c of hand) handCount[c] = (handCount[c] || 0) + 1;

    function removeConsecutive(s) {
        let i = 0;
        while (i < s.length) {
            let j = i;
            while (j < s.length && s[j] === s[i]) j++;
            if (j - i >= 3) {
                s = s.slice(0, i) + s.slice(j);
                i = 0;
            } else {
                i++;
            }
        }
        return s;
    }

    const memo = new Map();

    function dp(s, handCount) {
        if (s.length === 0) return 0;
        const key = s + JSON.stringify(handCount);
        if (memo.has(key)) return memo.get(key);
        let res = Infinity;
        let i = 0;
        while (i < s.length) {
            let j = i;
            while (j < s.length && s[j] === s[i]) j++;
            const ballsNeeded = 3 - (j - i);
            const c = s[i];
            if ((handCount[c] || 0) >= ballsNeeded) {
                handCount[c] = (handCount[c] || 0) - ballsNeeded;
                const newS = removeConsecutive(s.slice(0, i) + s.slice(j));
                const temp = dp(newS, handCount);
                if (temp !== -1) res = Math.min(res, ballsNeeded + temp);
                handCount[c] = (handCount[c] || 0) + ballsNeeded;
            }
            i = j;
        }
        memo.set(key, res === Infinity ? -1 : res);
        return memo.get(key);
    }

    return dp(board, handCount);
};

// Example usage:
console.log(findMinStep("WRRBBW", "RB")); // -1
console.log(findMinStep("WWRRBBWW", "WRBRW")); // 2

Line Notes

const ballsNeeded = 3 - (j - i);Calculate balls needed to remove group

if ((handCount[c] || 0) >= ballsNeeded)Check if hand has enough balls

handCount[c] = (handCount[c] || 0) - ballsNeeded;Use balls before recursion

const newS = removeConsecutive(...)Remove balls recursively after insertion

memo.set(key, res === Infinity ? -1 : res);Cache minimal moves or -1 if impossible

⏱

Complexity

TimeO(n^4 * m^5) due to interval splits and hand states

SpaceO(n^3 * m^5) for memoization

Interval DP splits board into subintervals and tries hand insertions, pruning with memo

💡 Though complex, this approach is the most efficient known for this problem within constraints.

Interview Verdict: Accepted - optimal approach for interviews

Demonstrates mastery of interval DP and memoization for game-like problems.

📊

All Approaches - One-Glance Tradeoffs

💡 Memoized recursion is good for quick implementation; interval DP is best for optimal performance and interview impressiveness.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O((n+m)*5^(n+m)) exponential	O((n+m)*5^(n+m)) recursion stack	Yes (deep recursion)	No	Mention only - never code
2. Memoized Recursion	O(n*m*5^(n+m)) with pruning	O(n*m*5^(n+m)) memo + stack	Possible but less likely	Yes with extra bookkeeping	Good for coding in interview
3. Interval DP with Memoization	O(n^4 * m^5)	O(n^3 * m^5)	No (controlled recursion)	Yes	Best approach to implement if time permits

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem constraints and examples.Step 2: Explain brute force recursion to show understanding.Step 3: Introduce memoization to optimize recursion.Step 4: Present interval DP as the optimal solution.Step 5: Discuss complexity and edge cases.

Time Allocation

Clarify: 3min → Brute Force: 5min → Memoization: 7min → Interval DP: 10min → Testing: 5min. Total ~30min

What the Interviewer Tests

Ability to identify overlapping subproblems, define DP states, implement memoization, and optimize interval splits.

Common Follow-ups

• What if hand size is very large? → Use pruning and heuristics.
• Can you reconstruct the sequence of insertions? → Store path in DP states.

💡 These follow-ups test deeper understanding of optimization and solution reconstruction.

🔍

Pattern Recognition

When to Use

1) Problem involves intervals or substrings; 2) Requires minimal moves or cost; 3) Has game-like insert/remove operations; 4) Overlapping subproblems with optimal substructure.

Signature Phrases

minimum number of movesinsert ballsremove consecutive ballschain reaction

NOT This Pattern When

Greedy or simple substring DP without removals or hand states

Similar Problems

Remove Boxes - similar interval DP with removalsBurst Balloons - interval DP with game-like removals

Practice

1. The following code attempts to implement the space-optimized DP solution for Maximal Square. Identify the line containing the subtle bug that causes incorrect results on some inputs.

def maximalSquare(matrix):
    if not matrix or not matrix[0]:
        return 0
    rows, cols = len(matrix), len(matrix[0])
    dp = [0] * (cols + 1)
    max_side = 0
    prev = 0
    for i in range(rows):
        for j in range(1, cols + 1):
            temp = dp[j]
            if matrix[i][j-1] == '1':
                dp[j] = 1 + min(dp[j], dp[j-1], prev)  # Bug here
                max_side = max(max_side, dp[j])
            else:
                dp[j] = 0
            prev = temp
    return max_side * max_side

medium

A. Line with 'dp[j] = 1 + min(dp[j], dp[j-1], dp[j-1])'

B. Line with 'temp = dp[j]'

C. Line with 'prev = temp'

D. Line with 'max_side = max(max_side, dp[j])'

Solution

1. Step 1: Identify the DP recurrence

   The recurrence requires min(dp[j], dp[j-1], prev), but code uses dp[j-1] twice, missing 'prev'.

2. Step 2: Understand impact

   Using dp[j-1] twice ignores the diagonal value 'prev', causing incorrect dp values and max square size.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct recurrence uses three distinct values [OK]

Hint: Check if all three DP states are used in min() [OK]

Common Mistakes:

• Forgetting to use 'prev' in min()
• Overwriting dp before using dependencies
• Incorrect dp initialization

2. What is the time complexity of the bottom-up dynamic programming solution for the minimum falling path sum problem on an n x n matrix?

medium

A. O(n^2) because each cell is processed once with constant neighbor checks

B. O(n) as only one row is stored at a time

C. O(3^n) since each step has three choices recursively

D. O(n^3) due to nested loops and checking three neighbors

Solution

1. Step 1: Identify loops in the bottom-up DP

   There are two nested loops: outer over rows (n), inner over columns (n).

2. Step 2: Analyze work per cell

   Each cell checks up to three neighbors in O(1) time, so total work is O(n * n) = O(n^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP processes each cell once with constant neighbor checks [OK]

Hint: Two nested loops over n rows and n columns [OK]

Common Mistakes:

• Confusing recursive exponential with DP complexity
• Assuming neighbor checks multiply complexity

3. Consider the following buggy code for Paint House (K Colors). Which line contains the subtle bug that can cause adjacent houses to have the same color, violating constraints?

medium

A. Line with 'min_prev = min(dp[x] for x in range(k))'

B. Line with 'dp = costs[0][:]' initialization

C. Line with 'new_dp = [0]*k' inside the loop

D. Line with 'return min(dp)' at the end

Solution

1. Step 1: Identify constraint violation

   The problem requires that adjacent houses cannot have the same color. The code must exclude the current color when computing min_prev.

2. Step 2: Locate bug in min_prev calculation

   The line 'min_prev = min(dp[x] for x in range(k))' includes the current color's dp value, allowing same color adjacency, violating constraints.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Excluding current color in min calculation is essential [OK]

Hint: Check if min excludes current color to avoid same-color adjacency [OK]

Common Mistakes:

• Including current color in min calculation
• Incorrect dp initialization
• Returning min(dp) without proper updates

4. Suppose the Burst Balloons problem is modified so that each balloon can be burst multiple times (reused), and bursting a balloon again yields coins based on the current adjacent balloons. Which of the following changes to the bottom-up DP approach correctly adapts to this variant?

hard

A. Switch to a stateful DP that tracks the count of bursts per balloon and use memoization over these counts

B. Modify the DP to consider only the first burst of each balloon and ignore reuse

C. Use the same interval DP but allow k to be chosen multiple times per interval

D. Use a greedy approach bursting the balloon with the maximum product of neighbors repeatedly

Solution

1. Step 1: Understand reuse impact

   Allowing multiple bursts per balloon means the problem state must track how many times each balloon has been burst, increasing complexity.

2. Step 2: Adapt DP state

   Interval DP assuming each balloon bursts once no longer works. We need a DP or memoization that tracks burst counts per balloon to correctly compute coins.

3. Step 3: Evaluate options

   Switch to a stateful DP that tracks the count of bursts per balloon and use memoization over these counts correctly proposes a stateful DP with counts and memoization. Use the same interval DP but allow k to be chosen multiple times per interval incorrectly reuses interval DP without state changes. Modify the DP to consider only the first burst of each balloon and ignore reuse ignores reuse, and D is greedy and incorrect.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Tracking burst counts is necessary for reuse variants [OK]

Hint: Reuse requires tracking burst counts, not just intervals [OK]

Common Mistakes:

• Trying naive interval DP for reuse
• Ignoring state explosion
• Using greedy for complex DP variants

5. Suppose the Dungeon Game is modified so that you can move right, down, or diagonally down-right at each step. Which of the following changes to the bottom-up DP solution correctly adapts to this variant?

hard

A. Change the dp recurrence to use min(dp[i+1][j], dp[i][j+1]) only, ignoring diagonal moves

B. Change the dp recurrence to min(dp[i+1][j], dp[i][j+1], dp[i+1][j+1]) and proceed similarly

C. Use a forward DP from start to end since diagonal moves break backward DP assumptions

D. Add an extra dimension to dp to track diagonal moves separately

Solution

1. Step 1: Understand new moves

   Allowing diagonal moves adds one more possible next cell from (i,j): (i+1,j+1).

2. Step 2: Update dp recurrence

   Minimum health needed at (i,j) depends on minimum among dp[i+1][j], dp[i][j+1], and dp[i+1][j+1].

3. Step 3: Keep backward DP approach

   Backward DP still works; just include diagonal cell in min calculation.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Including diagonal in min ensures correct health calculation [OK]

Hint: Add diagonal cell to min in dp recurrence [OK]

Common Mistakes:

• Ignoring diagonal moves
• Switching to forward DP unnecessarily
• Adding extra dp dimensions without need