50 DSA-Questions: #21, #22

#21. Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

public class Exercise21 {
    private static final String INPUT = "babad"; // substring: bab
    // private static final String INPUT = "cbbd"; // bb
    // private static final String INPUT = "9843798437398794abba454"; // 4abba4
    // private static final String INPUT = "rgttjtt45"; // ttjtt

    public boolean isPalindrome(String word) {
        return word.equals(new StringBuilder(word).reverse().toString());
    }

    private String processPalindrome(int i, int j, String result) {
        if (i < 0 || j > INPUT.length() - 1) {
            return result;
        }
        if (i == j || (i == j-1 && INPUT.charAt(i) == INPUT.charAt(j))) {
            String partialResult = i == j ? INPUT.charAt(i) + "" : INPUT.charAt(i) + "" + INPUT.charAt(j);
            return processPalindrome(i-1, j+1, partialResult);
        }
        String subWord = INPUT.charAt(i) + result + INPUT.charAt(j);
        if (isPalindrome(subWord)) {
            return processPalindrome(i-1, j+1, subWord);
        }
        return result;
    }

    private void solve() {
        String bestResult = INPUT.charAt(0) + "";
        for (int i=0; i<INPUT.length(); i++) {
            String palindromeOdd = processPalindrome(i, i, "");
            if (bestResult.length() < palindromeOdd.length()) {
                bestResult = palindromeOdd;
            }
            String palindromeEven = processPalindrome(i, i+1, "");
            if (bestResult.length() < palindromeEven.length()) {
                bestResult = palindromeEven;
            }
        }

        System.out.println(bestResult);
        // O(n^2)
    }

    public static void main(String args[]) {
        new Exercise21().solve();
    }
}

#22. Palindromic Substrings

Given a string s, return the number of palindromic substrings in it. A string is a palindrome when it reads the same backward as forward. 

public class Exercise22 {
    // private static final String INPUT = "abaffatr3r"; // 10 + 4 palindromic strings
    // private static final String INPUT = "racecar"; // 7 + 3 palindromic strings
    // private static final String INPUT = "abc"; // 3 palindromic strings
    private static final String INPUT = "aaa"; // 3 + 3 palindromic strings

    public int processPalindrome(int i, int j, String result, int count) {
        if (i < 0 || j > INPUT.length() - 1) {
            return count;
        }
        if (i == j || (i == j-1 && INPUT.charAt(i) == INPUT.charAt(j))) {
            String partialResult = i == j ? INPUT.charAt(i) + "" : INPUT.charAt(i) + "" + INPUT.charAt(j);
            return processPalindrome(i-1, j+1, partialResult, ++count);
        }
        String subWord = INPUT.charAt(i) + result + INPUT.charAt(j);
        if (new Exercise21().isPalindrome(subWord)) {
            return processPalindrome(i-1, j+1, subWord, ++count);
        }
        return count;
    }

    private void solve() {
        int count = 0;
        for (int i=0; i<INPUT.length(); i++) {
            int palindromeOddCount = processPalindrome(i, i, "", 0);
            count += palindromeOddCount;
            int palindromeEvenCount = processPalindrome(i, i+1, "", 0);
            count += palindromeEvenCount;
        }

        System.out.println(count);
    }

    public static void main(String args[]) {
        new Exercise22().solve();
    }
}