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

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

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.

Rust Solution

Rust's s.chars().collect() materialises a Vec<char> up front because a String can't be indexed by position — UTF-8 code points vary in width, so s[i] won't compile. The expand helper takes signed mut left: i32 / mut right: i32 so left can fall below 0 as the loop's own bound, and each access bridges back to the unsigned index type with s[left as usize] and (right as usize). Passing the buffer as &Vec<char> borrows it rather than moving or cloning, and the i as i32 casts at the call sites reconcile the usize loop counter with those signed pointers — friction the TS version never sees, since it indexes the string directly.

Go Solution

Go declares var expand func(l, r int) int and then assigns the closure to it, so expand captures s and n from the enclosing countSubstrings scope instead of threading them through as parameters. Indexing s[l] == s[r] reads raw bytes straight out of the string with no Vec<char> conversion — fine for the ASCII test input, though it compares bytes rather than runes. Plain signed int indices need no casts at all: l >= 0 guards the lower bound, r < n the upper, and l-- / r++ walk the two ends outward.