Count Palindromic Substrings

AlgorithmCodingGoldman SachsCitadelVoleonOnline AssessmentSoftware EngineerReported 2024-10-26single-report Frequency

medium

FreeAim for ~25 minTarget: O(n^2) time · O(1) space

Requirements

Input: one string, s.
Output the number of contiguous portions of s that read identically forward and backward. Count positions independently, so equal-looking substrings found at different locations each contribute to the result.

public int countPalindromicSubstrings(String s)

Boundary cases include an empty input, which produces 0, and a one-letter input, which produces 1.

Trace "aba" manually: it has 4 palindromic substrings (a, b, a, aba).
The challenge commonly numbered 647 covers the same task. The longest-palindromic-substring exercise commonly numbered 5 relies on the same core expansion pattern and is useful practice as well.

Hints (3)

AlgorithmCodingGoldman SachsCitadelVoleonOnline AssessmentSoftware EngineerReported 2024-10-26single-report Frequency

medium

FreeAim for ~25 minTarget: O(n^2) time · O(1) space

Input: one string, s.
Output the number of contiguous portions of s that read identically forward and backward. Count positions independently, so equal-looking substrings found at different locations each contribute to the result.

public int countPalindromicSubstrings(String s)

Boundary cases include an empty input, which produces 0, and a one-letter input, which produces 1.

Trace "aba" manually: it has 4 palindromic substrings (a, b, a, aba).
The challenge commonly numbered 647 covers the same task. The longest-palindromic-substring exercise commonly numbered 5 relies on the same core expansion pattern and is useful practice as well.

Hints (3)