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. What is the time complexity of the bottom-up dynamic programming solution for the Burst Balloons problem with input size n, and why?

medium

A. O(n^3) because for each interval we try all possible last balloons to burst

B. O(n^3) due to three nested loops iterating over intervals and burst positions

C. O(2^n) because of the exponential number of burst orders

D. O(n^2) because we fill a 2D dp table of size n by n

Solution

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

   There are three nested loops: length of interval (up to n), start index i (up to n), and position k (up to n) inside the interval.

2. Step 2: Calculate complexity

   Each loop runs up to n times, so total time is O(n * n * n) = O(n^3). The dp table is size O(n^2), but filling it requires the third loop over k.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Three nested loops over n -> O(n^3) time complexity [OK]

Hint: Three nested loops over intervals and positions cause cubic time [OK]

Common Mistakes:

• Confusing dp table size with time complexity
• Ignoring the innermost loop over k
• Assuming exponential time for DP solution

2. The following code attempts to solve the Triangle minimum path sum problem using bottom-up DP. Identify the line that contains a subtle bug causing incorrect results on some inputs.

medium

A. for i in range(len(triangle) - 2, -1, -1):

B. dp[j] = triangle[i][j] + min(dp[j + 1], dp[j])

C. dp = triangle[-1][:]

D. return dp[0]

Solution

1. Step 1: Examine dp update line

   The original code has dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]). The buggy code swaps the min arguments to min(dp[j + 1], dp[j]) which is harmless since min is commutative.

2. Step 2: Check for index out of bounds risk

   Accessing dp[j + 1] is safe because dp length is one more than current row length, so no out-of-bounds here.

3. Step 3: Identify subtle bug

   The subtle bug is that dp is updated in place from left to right, which can cause dp[j + 1] to be already updated when used in min, leading to incorrect results.

4. Step 4: Explanation of bug

   Because dp is updated from left to right, dp[j + 1] may have been updated in the current iteration, so min(dp[j], dp[j + 1]) uses a mixed state of dp values.

5. Step 5: Correct fix

   To fix, update dp from right to left so dp[j + 1] is not yet updated when used.

6. Final Answer:

   Option B -> Option B

7. Quick Check:

   Updating dp in wrong order causes subtle bugs [OK]

Hint: Bug usually in dp update line with min or indexing [OK]

Common Mistakes:

• Swapping min arguments (harmless but suspicious)
• Index out of bounds on dp[j+1]
• Updating dp in wrong order causing overwritten values

3. Suppose the problem changes so that you can move down to the same column or adjacent columns multiple times, but you want to find the minimum falling path sum where you can reuse rows multiple times (i.e., you can revisit rows). Which modification to the bottom-up DP approach correctly handles this variant?

hard

A. Use the original DP but memoize results to avoid recomputation

B. Use the same bottom-up DP but allow cycles by iterating until no dp changes occur

C. Switch to a shortest path algorithm like Bellman-Ford on a graph representing allowed moves

D. Apply greedy approach picking minimum adjacent values repeatedly

Solution

1. Step 1: Understand the variant with row reuse

   Allowing revisiting rows means cycles in the path graph, which breaks the acyclic assumption of DP.

2. Step 2: Identify suitable algorithm

   Model the problem as a graph with edges representing allowed moves and use Bellman-Ford to find shortest paths with possible cycles.

3. Step 3: Why other options fail

   Bottom-up DP assumes acyclic progression; greedy ignores global optimality; memoization doesn't handle cycles properly.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Bellman-Ford handles negative cycles and repeated nodes [OK]

Hint: Cycles require graph shortest path algorithms, not DP [OK]

Common Mistakes:

• Trying to reuse DP without cycle handling
• Assuming memoization solves cycles

4. Suppose the grid can contain negative numbers, and you want to find the minimum path sum from top-left to bottom-right moving only down or right. Which modification to the space-optimized DP approach is necessary to handle this correctly?

hard

A. Use the same DP approach since negative numbers do not affect correctness

B. Switch to a BFS or Dijkstra's algorithm to handle negative weights properly

C. Use top-down memoization with cycle detection to avoid infinite loops

D. Modify DP to track visited states and prevent revisiting cells

Solution

1. Step 1: Understand impact of negative numbers

   Negative numbers can create cycles with decreasing path sums if revisiting cells is allowed, causing infinite recursion.

2. Step 2: Recognize that moving only down or right prevents cycles

   Since moves are restricted to down or right, no cycles exist, so DP can still work, but negative values can cause incorrect min calculations if not handled carefully.

3. Step 3: Consider top-down memoization with cycle detection

   To be safe and handle any relaxed constraints (e.g., allowing revisits), top-down with memoization and cycle detection is necessary to avoid infinite loops.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Memoization with cycle detection prevents infinite recursion with negative weights [OK]

Hint: Negative weights require cycle detection in recursive solutions [OK]

Common Mistakes:

• Assuming DP always works with negative numbers
• Using BFS/Dijkstra without graph edges
• Ignoring possibility of cycles with negative weights

5. Suppose the polygon vertices can be reused multiple times in triangulation (i.e., vertices are not distinct points but can be repeated). How should the minimum score triangulation algorithm be modified to handle this?

hard

A. Use the same DP approach but allow k to iterate over all vertices, including i and j

B. Change the DP to a graph shortest path problem since reuse breaks polygon structure

C. Modify the DP to consider multisets of vertices and add memoization for repeated states

D. The problem becomes invalid as polygon vertices must be distinct; no modification possible

Solution

1. Step 1: Understand vertex reuse impact

   Reusing vertices breaks the polygon's simple structure; triangulation is no longer well-defined as a polygon.

2. Step 2: Identify correct approach

   The problem transforms into a graph problem where shortest paths or minimal cost cycles must be found, requiring a different algorithmic approach.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Reusing vertices invalidates polygon triangulation assumptions [OK]

Hint: Reusing vertices breaks polygon assumptions; DP no longer applies [OK]

Common Mistakes:

• Trying to reuse DP unchanged
• Ignoring polygon structure
• Assuming vertex reuse is trivial