Palindromic Substrings

NeetCode: Palindromic Substrings · LeetCode: 647. Palindromic Substrings · Difficulty: Medium

Given a string s, return how many of its substrings are palindromes. Substrings at different positions count separately, even if their text is equal.

Example

Text

Input:  s = "abc"    Output: 3    ("a", "b", "c")
Input:  s = "aaa"    Output: 6    ("a" x3, "aa" x2, "aaa")

Brute force: test every substring

isPalindrome(s, i, j) compares characters from both ends of the range i to j (exclusive) and stops at the first mismatch. It does not copy the substring.

Java

class Solution {
    private boolean isPalindrome(String s, int i, int j) { // s[i..j), j exclusive
        int l = i;
        int r = j - 1;
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }

    public int countSubstrings(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                if (isPalindrome(s, i, j)) {
                    count++;
                }
            }
        }
        return count;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.countSubstrings("abc"));
        System.out.println(solution.countSubstrings("aaa"));
        System.out.println(solution.countSubstrings(""));
    }
}

Output

3
6
0

Time: O(n^3). Space: O(1).

Optimal: expand around each center

Expand around each of the 2n - 1 centers, as in Longest Palindromic Substring, but count instead of tracking the longest. Each successful step outward from a center is one more palindrome, so a center that expands k times contributes exactly k palindromic substrings.

Java

class Solution {
    private int countFrom(String s, int l, int r) {
        int count = 0;
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            count++;
            l--;
            r++;
        }
        return count;
    }

    public int countSubstrings(String s) {
        int total = 0;
        for (int i = 0; i < s.length(); i++) {
            total += countFrom(s, i, i);     // odd length
            total += countFrom(s, i, i + 1); // even length
        }
        return total;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.countSubstrings("abc"));
        System.out.println(solution.countSubstrings("aaa"));
        System.out.println(solution.countSubstrings(""));
    }
}

Output

3
6
0

Time: O(n^2). Space: O(1). charAt returns a 16-bit char, and comparing two char values is exact because the input is lowercase English letters.