Minimum cyclic (forward or backward) shifts to be performed to the string to make it a palindrome

Question

Below is the problem statement and Solution. Two test cases failed for me. Help me figure it out.

A string is said to be palindrome, if it reads the same from both the ends. Given a string S, you are allowed to perform cyclic shifts. More formally, you can pick any one character from any end (head or tail) and you can append that character at the other end. For example, if the string is "abc", then if we do a shift using the character at head position then the string becomes "bca". Similarly, if we do the shift using the character at the tail then the input string becomes "cab". Your task is to find out the minimum number of shifts needed to make the given string, a palindrome. In case, we can't convert the string to palindrome then print -1.

Input Format: First line starts with T i.e. number of test cases, and then T lines will follow each containing a string S.

Output Format: Print the minimum number of cyclic shifts for each string if it can be made a palindrome, else -1.

Constraints: 1<=T<=100, 1<=|S|<=300, S will contains only lower case alphabets ('a'-'z').

Sample Input and Output

Input

4
abbb
aaabb
aabb
abc

Output

-1
1
1
-1

Explanation: For Test Case 2 (aaabb): Shift the character at the tail to the head and the result will be "baaab", which is a palindrome. This is an operation which requires minimum number of shifts to make the given string a palindrome.

For Test Case 3 (aabb): One way to convert the given string to palindrome is, shift the character at the head to the tail, and the result will be "abba", which is a palindrome. Another way is to shift the character at the tail to the head, and the result will be "baab", which is also a palindrome. Both require only one shift.

public class cyclic {

    static boolean flag = false;

    // fn to check if string is palindrome
    static boolean ispal(String s) {
        String reverse = "";
        int length = s.length();
        for (int i = length - 1; i >= 0; i--)
            reverse = reverse + s.charAt(i);
        reverse = reverse.trim();
        if (s.equals(reverse)) {
            flag = true;
            return true;
        } else {
            return false;
        }
    }

    // fn to perform front shift
    static int frontshift(String str) {
        int count = 0;
        String element = "";
        String s1[] = str.split("");
        Deque<String> dequeA = new LinkedList<String>();
        for (int i = 1; i < s1.length; i++) {
            dequeA.add(s1[i]);
        }
        while (!ispal(str)) {
            if (count <= str.length()) {
                element = "";
                String firstElement = dequeA.removeFirst();
                dequeA.addLast(firstElement);
                for (String object : dequeA) {
                    element = element + object;
                }
                str = element;
                count++;
            } else {
                break;
            }
        }
        return count;
    }

    // fn to perform backshift
    static int backshift(String str) {
        int count = 0;
        String element = "";
        String s1[] = str.split("");
        Deque<String> dequeA = new LinkedList<String>();
        for (int i = 1; i < s1.length; i++) {
            dequeA.add(s1[i]);
        }
        while (!ispal(str)) {
            if (count <= str.length()) {
                element = "";
                String firstElement = dequeA.removeLast();
                dequeA.addFirst(firstElement);
                for (String object : dequeA) {
                    element = element + object;
                }
                str = element;
                count++;
            } else {
                break;
            }
        }
        return count;
    }

    public static void main(String args[]) throws IOException {
        BufferedReader br =
                new BufferedReader(new InputStreamReader(System.in));
        List<Integer> list = new ArrayList<Integer>();
        int range = Integer.parseInt(br.readLine());
        for (int i = 0; i < range; i++) {
            String s = br.readLine();
            int l1 = frontshift(s);
            int l2 = backshift(s);
            if (flag == true) {
                if (l1 <= l2) {
                    list.add(l1);
                } else {
                    list.add(l2);
                }
            } else {
                list.add(-1);
            }
            flag = false;
        }
        for (Integer integer : list) {
            System.out.println(integer);
        }
    }
}

Answer 1

I solved your task not based on your code:

import java.util.Scanner;

public class PalyndromeTest {
    static boolean isPalyndrome(String s, int shift) {
        int n = s.length();
        if(shift < 0) shift+=n;
        for(int pos = 0; pos < n/2; pos++) {
            if(s.charAt((pos+shift)%n) != s.charAt((n-pos-1+shift)%n))
                return false;
        }
        return true;
    }

    static int findShift(String s) {
        for(int shift = 0; shift <= s.length()/2; shift++) {
            if(isPalyndrome(s, shift) || isPalyndrome(s, -shift))
                return shift;
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int count = s.nextInt();
        s.nextLine();
        for(int i=0; i<count; i++) {
            System.out.println(findShift(s.nextLine()));
        }
    }
}

First, isPalyndrome method. It checks whether the string is palyndrome and works with positive or negative shifts as well. Note that, for example, for string of length 5, shift = -1 is the same as shift = 4. We don't create any new strings, we just scan the existing one using the String.charAt method. We use % n remainder operator to automatically move back to the string beginning when the string end is reached. Note that we should check only the half of the string.

Second, the findShift method. It just iterates over all the shifts from 0 to s.length()/2 (bigger shifts are unnecessary to check as they are equal to the already checked negative shifts). On every iteration it checks both positive and negative shift.

Finally the main method which reads the standard input and calls the findShift for each input line. It outputs the result immediately, though if you want, you may collect it to the list and output at the end.