Problem Statement: Given an integer array arr, in one move you can select a palindromic subsequence arr[i], ..., arr[j] where 0 <= i <= j < arr.length, and remove that subsequence from the given array. Note that after removing a subarray, the elements move to remove the gap between them.
Return the minimum number of moves needed to remove all numbers from the array.
Solution:
import java.util.*;
class Solution {
public int minimumMoves(int[] arr) {
int N = arr.length;
int max = 1;
int min = Integer.MAX_VALUE;
List<Integer> A = new ArrayList<>();
for (int i = 0; i < arr.length; i++) A.add(arr[i]);
int count = 0;
while(A.size() > 0) {
boolean hasPalindrome = false;
List<Integer> elements = new ArrayList<>();
for (int i = 0; i < (1<<N); i++) {
List<Integer> combination = new ArrayList<>();
for (int j = 0; j < A.size(); j++) {
if ((i & (1 << j)) > 0) {
combination.add(j);
}
}
if (isPalindrome(A, combination) && (combination.size() > max) && getCharactersToRemove(A, combination) < min) {
hasPalindrome = true;
max = combination.size();
min = getCharactersToRemove(A, combination);
elements = new ArrayList<>(combination);
if (getCharactersToRemove(A, combination) == 0) { break;}
} else {
// System.out.println("A: " + print(A) + " Elements: " + print(elements) + " Combination: " + print(combination) + "isPalindrome=" + String.valueOf(isPalindrome(A, combination)) + " getCharsToRemove=" + getCharactersToRemove(A, combination) + " min = " + min);
}
}
if (!hasPalindrome) {
count += 1;
A.remove(A.size() - 1);
} else {
count += getCharactersToRemove(A, elements) + 1;
A = removeCharacters(A, elements);
// System.out.println("Removing " + count + " characters at indices:" + print(elements) + " and remaining elements: " + print(A));
// elements = new ArrayList<>();
max = 1;
min = Integer.MAX_VALUE;
}
}
return count;
}
public boolean isPalindrome(List<Integer> A, List<Integer> combination) {
int start = 0;
int end = combination.size()-1;
while (start <= end) {
if (A.get(combination.get(start)) != A.get(combination.get(end))) {
return false;
}
start++;
end--;
}
return true;
}
public int getCharactersToRemove(List<Integer> A, List<Integer> combination){
if (combination.size() < 2) return 0;
List<Integer> clone = new ArrayList<>(A);
return removeCharacters(clone, combination).size();
}
public List<Integer> removeCharacters(List<Integer> A, List<Integer> combination) {
int start = 0;
int end = combinations.size()-1;
int last = 0;
while (start <= end) {
for (int i = last; i< A.size(); i++) {
if (A.get(i) == combination.get(start)) {
A.set(I, Integer.MAX_VALUE);
last = i+1;
start++;
}
}
}
List<Integer> result = new ArrayList<>();
For (int I = 0; I < A.size(); i++) {
if (A.get(i) != Integer.MAX_VALUE) {
result.add(A.get(i));
}
}
return result;
}
public List<Integer> removeCharacters(List<Integer> A, List<Integer> combination) {
int start = combination.get(0);
int end = combination.get(combination.size()-1);
List<Integer> result = new ArrayList<>();
if (start > 0){
result.addAll(A.subList(0, start));
}
if (end < A.size() - 1) {
result.addAll(A.subList(end + 1,A.size()));
}
return result;
}
public String print(List<Integer> elements){
StringBuilder sb = new StringBuilder();
for (int i = 0; i < elements.size(); i++) {
sb.append(elements.get(i) + " ");
}
return sb.toString();
}
}
Examples:
A = [-1,0,1] => 3
A = [-1,0,-1] => 1
A = [-1] => 1
A = [-1,0] => 2
A = [0,0] => 1
A = [1,0,1,2,3] => 3
A = [-2,-1,0,1,0] => 3
