CodingGyan

Count Palindromic Substrings

medium Strings

Problem

Count how many parts of the word (continuous pieces, each position choice counted separately) read the same forwards and backwards. A single letter is a palindrome. Print the count.

Constraints

  • 1 <= length <= 1000
  • lowercase letters

Examples

Input

aaa

Output

6

Solutions

Best approachTime O(n^2)Space O(1)

We move outward from each center while both ends match. Each successful step is one more palindrome. There are 2n - 1 centers and each expands at most n steps, so O(n^2) time and O(1) memory.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Count palindromic parts.
 * Input   : One word.
 * Output  : The count.
 * Approach: Expand around centers.
 * Time    : O(n^2)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        private static int expand(String s, int left, int right) {
            int found = 0;
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                found++;
                left--;
                right++;
            }
            return found;
        }

    // This method solves the task. It receives the input and returns the answer.
    static int solve(String s) {
        // Step 1: Every palindrome has a center. It is one letter (odd length) or the gap between two letters (even length).
        int count = 0;
        for (int center = 0; center < s.length(); center++) {
            count += expand(s, center, center);
            count += expand(s, center, center + 1);
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.hasNextLine() ? scanner.nextLine() : "";
        System.out.println(solve(s));
    }
}
Hints (2)
  1. How many centers does a word of length 4 have?
  2. When do we stop expanding?