#codingexercise
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.
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();
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;
int start = combination.get(0);
int end =
combination.get(combination.size()-1);
int count = 0;
for (int i = start+1; i < end; i++)
{
if (combination.contains(i) ==
false){
count++;
}
}
return count;
}
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();
}
No comments:
Post a Comment