Solving Palindromic Substrings: Counting Symmetrical Sequences

The "Palindromic Substrings" problem involves identifying and counting all the substrings within a given string that are palindromes.

Problem Statement

Given a string s, return the number of palindromic substrings in it. A substring is palindromic if it reads the same forward and backward.

Example

• Input: "abc"
• Output: 3 (The palindromic substrings are: "a", "b", "c")
• Input: "aaa"
• Output: 6 (The palindromic substrings are: "a", "a", "a", "aa", "aa", "aaa")

Solution Approach - Expand Around Center

function countSubstrings(s: string): number {
  let count = 0;

  for (let i = 0; i < s.length; i++) {
    count += expandAroundCenter(s, i, i); // Odd length palindromes
    count += expandAroundCenter(s, i, i + 1); // Even length palindromes
  }

  function expandAroundCenter(str: string, left: number, right: number): number {
    let tempCount = 0;
    while (left >= 0 && right < str.length && str[left] === str[right]) {
      tempCount++;
      left--;
      right++;
    }
    return tempCount;
  }

  return count;
}

Breaking Down the Solution

• Center Expansion Technique: For each character, consider it as the center of potential odd and even length palindromes.
• Counting Palindromes: Expand around each center and count valid palindromic substrings.
• Iterative Process: Accumulate the count of palindromic substrings for each expansion.

Optimised solution

function countSubstrings(s: string): number {
  let count = 0;

  for (let i = 0; i < s.length; i++) {
    // Check for odd length palindromes
    count += countPalindromesAroundCenter(s, i, i);
    // Check for even length palindromes
    count += countPalindromesAroundCenter(s, i, i + 1);
  }

  return count;
}

function countPalindromesAroundCenter(s: string, left: number, right: number): number {
  let count = 0;
  while (left >= 0 && right < s.length && s[left] === s[right]) {
    count++; // Increment count for each palindrome found
    left--; // Expand to the left
    right++; // Expand to the right
  }
  return count;
}

Optimizations:

1. Focused Function: The countPalindromesAroundCenter function is dedicated solely to counting palindromic substrings, making the code more modular and easier to understand.
2. Single Responsibility: Each call to countPalindromesAroundCenter checks either odd or even length palindromes. This separation makes it clear what each function call is responsible for.
3. Efficient Expansion: The function expands around the center only as long as it finds palindromic substrings, minimizing unnecessary checks.

This approach retains the O(n^2) complexity, as in the worst case (like a string of identical characters), it must still expand around each character. However, it's more efficient in terms of operations performed for each expansion.

Conclusion

The Palindromic Substrings problem is a compelling challenge in string processing, demonstrating a methodical approach to identify and count symmetric patterns within a string.