Friday, June 7, 2024

 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


No comments:

Post a Comment