How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Reevo.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Reevo during technical interviews.

Count all palindromic substrings | Reevo Coding Question

Quick Overview

This question evaluates proficiency with string algorithms and algorithmic problem-solving, focusing on palindrome detection and counting contiguous substrings. It is commonly asked to assess implementation skills and the ability to reason about time and space complexity within the Coding & Algorithms domain, emphasizing practical application rather than purely conceptual understanding.

Count all palindromic substrings

Company: Reevo

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

Given a string `s`, count how many substrings of `s` are palindromes. - A substring is a contiguous block of characters. - A palindrome reads the same forward and backward. - Count **all** palindromic substrings (including duplicates by position). Return the total count. Constraints (typical): `1 ≤ |s| ≤ 2000` (so an `O(n^2)` approach is acceptable).

Quick Answer: This question evaluates proficiency with string algorithms and algorithmic problem-solving, focusing on palindrome detection and counting contiguous substrings. It is commonly asked to assess implementation skills and the ability to reason about time and space complexity within the Coding & Algorithms domain, emphasizing practical application rather than purely conceptual understanding.

Given a string `s`, count how many substrings of `s` are palindromes. - A **substring** is a contiguous block of characters. - A **palindrome** reads the same forward and backward. - Count **all** palindromic substrings, counting duplicates that occur at different positions separately. Return the total count. **Example 1:** ``` Input: s = "abc" Output: 3 Explanation: The palindromic substrings are "a", "b", "c". ``` **Example 2:** ``` Input: s = "aaa" Output: 6 Explanation: "a", "a", "a", "aa", "aa", "aaa". ```

Constraints

1 <= |s| <= 2000
s consists of lowercase (and/or any printable) characters
An O(n^2) approach is acceptable

Examples

Input: "abc"

Expected Output: 3

Explanation: Each single character is a palindrome: "a", "b", "c". No longer substring is a palindrome.

Input: "aaa"

Expected Output: 6

Explanation: Three single chars ("a" x3), two "aa", and one "aaa" = 6.

Hints

Every palindrome has a center. For a string of length n there are 2n-1 possible centers: n single-character centers (odd-length palindromes) and n-1 gaps between characters (even-length palindromes).
From each center, expand outward with two pointers while the characters on both sides match; every successful expansion yields one more palindromic substring.
This center-expansion runs in O(n^2) time and O(1) extra space, which fits the |s| <= 2000 constraint comfortably.