3
\$\begingroup\$

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));
}

}
\$\endgroup\$
  • 1
    \$\begingroup\$ Where did you get this problem from? Looking at the problem statement here, I'd say you're missing the optimal substring "3456546" which can be rearanged into "4563654". \$\endgroup\$ – Imus Nov 23 '17 at 8:42
  • 1
    \$\begingroup\$ Hi, thanks for the reply. The problem statement mentions that only even length palindromes are expected, so that rules out "3456546" \$\endgroup\$ – eshi14 Nov 23 '17 at 10:35
  • \$\begingroup\$ "Input is one line String which contains only integers" a string does not contain integers but characters and the characters 0,...,9 are called decimal digits. So your input is a string that consists of decimal digits only. \$\endgroup\$ – miracle173 Nov 24 '17 at 2:30
  • \$\begingroup\$ A string can be arranged in an even length palindrome if the number of occurrences of a digit in the string is an even number. So you are looking for the longest substring where the number of occurrences of each digit is an even number. \$\endgroup\$ – miracle173 Nov 24 '17 at 2:51
  • \$\begingroup\$ exactly miracle173 !! \$\endgroup\$ – eshi14 Nov 27 '17 at 7:57
1
\$\begingroup\$

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);
    }
}
\$\endgroup\$
  • \$\begingroup\$ Also, there are opportunities to stop earier, for example, if maxSIze > ( length - i ) etc. \$\endgroup\$ – RobAu Nov 23 '17 at 14:39
  • \$\begingroup\$ -1 1. A code review should review the code of the OP. This is not a place tu post your solutions of a problem. 2. "You need to find the longest substring that is an even palindrome" no, that is wrong, You need to find the longest substring that could be arranged to a palindrome. that is not the same. \$\endgroup\$ – miracle173 Nov 24 '17 at 2:43
  • \$\begingroup\$ Thank you miracle for explaining your down vote and pointing out my mistake in my text, as you might have noticed the code and text are now agree. OP asked for other data structures and optimization, so I explained what I think should be the algorithmic approach, and provided two examples. \$\endgroup\$ – RobAu Nov 24 '17 at 6:10
  • \$\begingroup\$ Thanks RobAu for the tips, sorry for the delayed response .. \$\endgroup\$ – eshi14 Nov 27 '17 at 7:54
  • \$\begingroup\$ @eshi14 no worries. Glad I could help. \$\endgroup\$ – RobAu Nov 27 '17 at 8:09
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.