Palindrome Removal - Practice Coding Problems

Palindrome Removal - Problem

You are given an integer array arr. In one move, you can select a palindromic subarray arr[i], arr[i + 1], ..., arr[j] where i ≤ j, and remove that subarray from the given array.

Note that after removing a subarray, the elements on the left and on the right of that subarray move to fill the gap left by the removal.

Return the minimum number of moves needed to remove all numbers from the array.

Input & Output

Example 1 — Mixed Elements

$ Input: arr = [1,3,4,1,5]

› Output: 3

💡 Note: Remove [4] (1 move), then remove [1,3,1] which becomes palindromic (1 move), finally remove [5] (1 move). Total: 3 moves.

Example 2 — All Same

$ Input: arr = [1,1,1,1]

› Output: 1

💡 Note: The entire array is palindromic, so we can remove it in 1 move.

Example 3 — Single Element

$ Input: arr = [5]

› Output: 1

💡 Note: Single element is palindromic, remove in 1 move.

Constraints

1 ≤ arr.length ≤ 100
1 ≤ arr[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array [1,3,4,1,5] needs to be completely removed

Find Palindromes

Identify palindromic subarrays: [1], [3], [4], [1], [5], [1,3,1]

Optimal Partition

Best way: remove [4], then [1,3,1], then [5] = 3 moves

Key Takeaway

🎯 Key Insight: Use dynamic programming to find optimal palindromic partitioning

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to use dynamic programming to find the optimal way to partition the array into palindromic subarrays. Best approach is 2D Dynamic Programming with palindrome preprocessing. Time: O(n³), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursion	O(3ⁿ)	O(n)	Try all possible palindromic removals recursively
Memoized Recursion	O(n³)	O(n²)	Add memoization to avoid recomputing same subproblems
Dynamic Programming (Bottom-up)	O(n³)	O(n²)	Bottom-up DP table to build solution iteratively

Brute Force Recursion — Algorithm Steps

Check all possible subarrays
For each palindromic subarray, remove it
Recursively solve for remaining parts
Return minimum moves

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Array

Start with the full array [1,3,4,1,5]

Find Palindromes

Check each possible starting palindrome: [1], [1,3], [1,3,4], etc.

Recursive Split

For each valid palindrome, recursively solve the remaining parts

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int isPalindrome(int* arr, int start, int end) {
    while (start < end) {
        if (arr[start] != arr[end]) {
            return 0;
        }
        start++;
        end--;
    }
    return 1;
}

int solve(int* arr, int start, int end) {
    if (start > end) {
        return 0;
    }
    
    int minMoves = INT_MAX;
    
    // Try all possible palindromic subarrays starting from start
    for (int i = start; i <= end; i++) {
        if (isPalindrome(arr, start, i)) {
            // Remove palindrome arr[start:i+1] and solve for remaining
            int moves = 1 + solve(arr, i + 1, end);
            if (moves < minMoves) {
                minMoves = moves;
            }
        }
    }
    
    return minMoves;
}

int solution(int* arr, int n) {
    return solve(arr, 0, n - 1);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    int arr[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int num = atoi(token);
        arr[n++] = num;
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(arr, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(3ⁿ)

For each subarray, we have 3 choices: include in left part, include in right part, or remove as palindrome

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth can go up to n levels

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler