Find a substring which could be rearranged into a palindrome

Question

Problem statement:

To find maximum length substring in an input string which could be arranged into a palindrome, only even length palindromes are expected.

Input is one line String which contains only integers.

Output is the length of the substring which could be arranged in palindrome.

Example:

Input: 123456546

Output: 6 (substring 456546 can be rearranged to an even palindrome)

My approach (I am not sure if this is the most optimal way to do it, please point out any modifications):

1. Find the integers which are occurring in pairs in the original input string
2. For each possible length look for a possible palindrome by starting from each integer (which we listed earlier as possible palindrome members) and searching for the required length.

Although this approach and the code works, I don't think it is optimal at all (I am using multiple nested for loops and the code doesn't look good at all). Should I use some other data structures? Can someone please help in optimising the solution?

public class Code2 {
public static int lengthofPalindrome(String input1)
{
    /*Check if the input is valid
     * return 0 :   if length = 0 , 
     *              contains anything other than numbers
     * */
   if(input1.length() <= 0 ) 
       return 0;
   if (input1.matches("[0-9]+"))
       ;
   else 
       return 0;


  Integer[] input_array  = new Integer[input1.length()]; // copy of the input string used to compare
  List<Integer> input_array_2 = Arrays.asList(input_array); //copy of the input string in array list 
  List<Integer> tempString = new ArrayList(); // temp arrayList 

  List<Integer> sub1 = new ArrayList(); // contains unique digits getting repeated 2 times
  List<Integer> sub2 = new ArrayList(); // contains all digits getting repeated 2 times

  int flag_2 =0;
  //copy the string into integer array
  for (int i = 0 ; i < input1.length(); i ++) {
      input_array[i] = Integer.parseInt(String.valueOf(input1.charAt(i)));    
  }
 //find the int which have even occurences in the input array and populate sub1 arrayList with the values
  for(int i =0 ; i < input1.length(); i++) {
      if(i==0) {
          tempString.add(input_array[0]);
      }
      else {
          for(int j = 0; j <tempString.size(); j++) {
              if(input_array[i]==tempString.get(j)) {
                  tempString.remove(j);
                  sub1.add(input_array[i]);
                  tempString.add(j, -2);
                  flag_2 = 1;
              }
              if(flag_2 ==1) {
                  break;
              }
          }
          if(flag_2 ==1) {
              flag_2=0;
          }
          else {
              tempString.add(input_array[i]);
          }
      }

  }

  //Make a copy of sub1 and populate sub2
  for(Integer a : sub1) {
    sub2.add(a);
}

  //Remove duplicates from the sub1
for (int i =0 ; i < sub1.size(); i ++) {
    for(int j =i+1 ; j <sub1.size();j++) {
        if(sub1.get(i)==sub1.get(j)) {
            sub1.remove(j); 
        }
    }
}

/*Length of sub2: used to calculate the legths of possible pallindrome substrings
 Eg. If the length of sub2(contains the ints which occur in pairs in the input string) = 3
 Lengths of possible substrings : 6, 4, 2 
*/
int length = sub2.size();

int  value =0;
// value is the length of the substring that can be rearranged as a palindrome
for (int i =length; i >= 1; i--) {
    value = find_sub(i*2, sub1,input_array_2 );
    if(value !=0) {
        break;
    }

}
return value;   

}


/*Parameters
 * length       : Length of the substring to be found
 * subString    : Contains the int which could be part of the substring
 * input1       : Original input string 
 * This function finds the length of the substring of given length inside the main String, if it exists otherwise returns 0 
 * */

public static int find_sub(int length, List<Integer> subString, List<Integer> input1) {
    if(length ==0 || subString.size() == 0 || input1.size()==0) {
        return 0;
    }
    int index = -2;
    int sum = 0;
    List<Integer> allIndex = new ArrayList<Integer>();
    int breakFlag =-2;

    // List of all the indices of input1 string which are present in subString (occur in pair)
    for(int j =0; j < subString.size();j++) {

    for (int i =0; i < input1.size();  i ++) {
        if (input1.get(i) == subString.get(j)) {
            allIndex.add(i);
        }
      }
    }
    Collections.sort(allIndex);
    // Store the values of the integer elements and its occurence if the substring exists
    Map<Integer, Integer> palin ;
    int val, finalFlag =-2;
    int bound;
    List<Integer> subList= new ArrayList<Integer>();

    // Main loop to chcek from each index value for the substring of desired length 
    for(int j =0; j < allIndex.size(); j++) {
        //gets the first index of the substring
        index = allIndex.get(j);

        //check if the length to search doesnot fit in the main string break;
        if(index+length-1 >= input1.size()) {
            break;
        }


        //make a sublist with the desired length
        subList = input1.subList(index, index+length-1);
        //check if the substring of given length contain anything other than the ints in the subString
        for(int i =0; i < subList.size(); i++) {
            for(int m =0 ; m < subString.size(); m++) {
                if(subList.get(i)==subString.get(m)) {
                    breakFlag =0;
                    break;
                }
                else {
                    breakFlag =1;
                }
            }
            //subList contains other int 
            if(breakFlag ==1) {
                break;
            }
        }

            //breakFlag : is set when the substring in input1 contains any other integer than what is expected (subString)
            if(breakFlag ==0) {
                //logic to check if the pallindrome can be formed from this index and this length
                //add all the recuring values in the map with number of occurences
                palin= new HashMap<Integer, Integer>();
                for(int n =index; n <= index+length-1; n++) {
                    if(palin.containsKey(input1.get(n))) {
                        val = palin.get(input1.get(n));
                        palin.put(input1.get(n), val+1);                        }
                    else {
                        palin.put(input1.get(n), 1);
                    }
                }

                for(Map.Entry<Integer, Integer> entry: palin.entrySet()) {
                }
                sum=0;
                for(Map.Entry<Integer, Integer> entry: palin.entrySet()) {
                    if(entry.getValue() %2 !=0) {
                        finalFlag = 0;
                        break;
                    }
                    else {
                        //string can be rearranged into a pallindrome
                        finalFlag =1;
                        sum = sum+entry.getValue();
                        }
                }
            }
        if(finalFlag ==1) {
            break;
        }
    }
    if(finalFlag ==1) {
        return sum;
    }
    else
    return 0;
}
public static void main(String[] args) throws IOException{
    Scanner in = new Scanner(System.in);
    int output = 0;
    String ip1 = in.nextLine().trim();
    output = lengthofPalindrome(ip1);
   System.out.println(String.valueOf(output));
}

}

Answer 1

Observations

You need to find the longest substring that can be arranged into an even palindrome. Basically, you can split the problem in: making all substrings, and check for each one if that can be arranged into a palindrome.

That is inefficient, as you make a lot of new String objects. So it is better to just use the characters and see if the character-frequency is OK. (all freqencies must be even). Because scanning each character only increases the freqency of that given character, we can quickly check if the substring starting from i until j is a even palindrome.

So, we need two loops, one for the substring start, and a nested one from the substring-end.

Observation 2

As the input can only be 0..9, you could also use an int[] for the frequencies. This is a bit better for the performance, but the main algorithm does not change with that.

Observation 3

As you are only interested in even/uneven, you could also implement this as a bitmask, flipping each ith bit when you encounter a integer i. This is probably most efficient, as you only need a short to store the 'isPalinDrome' state. The length of the palindrome can be calculated by j-i+1. (if i=0 and j=1 we got 2 characters, at position 0 and 1)

Proposed solution

I skipped all the validation, and cut right to the algorithm.

import java.util.HashMap;
import java.util.Map;

public class LongestPalindromeCandidate {

    /** Palindrome is possible if all frequencies as even, or all even except 1 */
    public static boolean isPalinDromePossible(Map<Character, Integer> freqMap) {
        int countUneven = (int) freqMap.values().stream().filter(i -> i % 2 == 1).count();
        return countUneven < 1;
    }

    public static void main(String[] args) {
        String test = "123456546";

        int maxSize = 0;

        //create all sub-string frequencies starting from i
        for (int i = 0; i < test.length() - 1; i++) {
            Map<Character, Integer> freqMap = new HashMap<Character, Integer>();

            //let the sub-string go to j
            for (int j = i ; j < test.length(); j++) {

                //each time we encounter a character, we add it to the substring-from-i frequency-map
                char ch = test.charAt(j);

                //increate the freq. by one, setting it to 1 if it not already in the map
                freqMap.compute(ch, (k, v) -> v == null ? 1 : v + 1);

                //check if the freq.map is a palindrome. If so, we can check if it is longer than the current max
                if (isPalinDromePossible(freqMap)) {
                    int size = freqMap.values().stream().mapToInt(k -> k).sum();
                    if (size > maxSize) {
                        maxSize = size;
                    }

                    //just for debugging
                    System.out.println("Palindrome possible:" + freqMap.keySet());
                }
            }

        }
        System.out.println("Maxsize:" + maxSize);
    }
}

Bit flipping solution for performance and fun :)

public class LongestPalindromeCandidate2 {

    public static void main(String[] args) {
        String test = "123456546";
        int length = test.length();

        int[] input = new int[length];

        for (int i=0; i<input.length; i++)
        {
            input[i] = test.charAt(i) - '0';
        }

        int maxSize = 0;

        //create all sub-string frequencies starting from i
        for (int i = 0; i < length - 1; i++) {

            int parity =0;

            //let the sub-string go to j
            for (int j = i ; j < length; j++) {

                int n = input[i];

                //flip the nth bit
                parity = parity ^ (1 << n);

                //check if parity indicates an even palindrome. If so, we can check if it is longer than the current max
                if (parity == 0) {
                    if ((j-i +1 ) >  maxSize) {
                        maxSize = (j-i+1 );
                    }
                }
            }
        }
        System.out.println("Maxsize:" + maxSize);
    }
}

Answer 2

The OP asked for other approaches.

An algorithm idea based on @RobAu's bit-flipping solution: a "palindromable" substring is between two places where the accumulated bit-flipping patterns are equal. Using a map of bit pattern occurrences, this can be done in one linear run.

In a linear run, create a map bit-pattern -> first index where this bit pattern was reached. If you encounter a bit pattern already contained in the map, use the index from the map and the current index as a potential substring. Keep the longest of these substrings.

If you're expecting very long strings (> 1000), instead of the map, an array[1024] indexed by the bit pattern might be faster.