codelessgenie blog

Counting Three Non-Overlapping Substrings that Form a Palindrome

Palindromic strings—sequences that read the same forwards and backwards—are foundational in computer science with applications in areas like DNA sequencing and data validation. This blog explores an advanced variant: finding three non-overlapping substrings within a string that form a palindrome when concatenated. We'll dive into problem analysis, intuition, efficient solutions, and practical optimizations.

2026-07

Table of Contents#

  1. Problem Statement
  2. Key Observations and Challenges
  3. Brute-Force Approach
  4. Optimized Approach Using Hashing and Palindromic Properties
  5. Complexity Analysis
  6. Step-by-Step Example
  7. Best Practices and Common Pitfalls
  8. Conclusion
  9. References

1. Problem Statement#

Given a string s of length n, count all triplets (i, j, k) such that:

  • The substrings s1 = s[i:i+a], s2 = s[j:j+b], s3 = s[k:k+c] are non-overlapping.
  • The concatenation s1 + s2 + s3 forms a palindrome.
  • a, b, c are positive integers where a + b + c is the length of the concatenated string.

Constraints:

  • ( 3 \leq n \leq 200 )
  • s consists of lowercase English letters.

Example:

  • For s = "abcbab", the triplet (1, 3, 5) with substrings "ab", "c", "ba" forms "abcba", which is a palindrome.

2. Key Observations and Challenges#

Palindromic Structure#

For X + Y + Z to be a palindrome:

  • ( \text{reverse}(X) = Z )
  • Y must itself be a palindrome.

This simplifies our task to finding:

  1. A center substring Y that is a palindrome.
  2. Prefix X and suffix Z such that ( \text{reverse}(X) = Z ).

Non-Overlapping Constraint#

Substrings must satisfy:

  • End of s1 ≤ Start of s2
  • End of s2 ≤ Start of s3

Challenges:#

  • High Computational Cost: Naïve solutions scale as ( O(n^6) ).
  • Overhead in Concatenation: Repeatedly checking palindromes is inefficient.

3. Brute-Force Approach#

Methodology#

Iterate through all possible start and end positions for three non-overlapping substrings:

def brute_force(s):
    n = len(s)
    count = 0
    # Iterate over all possible substring positions
    for a in range(1, n - 1):          # Length of s1
        for b in range(1, n - a - 1):  # Length of s2
            c = n - a - b              # Length of s3
            for i in range(0, n - a + 1):      # Start of s1
                j = i + a                           # Start of s2
                for k in range(j + b, n - c + 1):   # Start of s3
                    s1 = s[i:i+a]
                    s2 = s[j:j+b]
                    s3 = s[k:k+c]
                    concat = s1 + s2 + s3
                    if concat == concat[::-1]:
                        count += 1
    return count

Limitations:

  • Time complexity: ( O(n^6) ) (six nested loops).
  • Impractical for ( n \geq 50 ).

4. Optimized Approach Using Hashing and Palindromic Properties#

Core Idea#

Exploit the structure of palindromic concatenation:

  1. Center Palindrome (s2): Precompute palindromic substrings.
  2. Matching Prefix-Suffix (s1 and s3): Use rolling hashes (Rabin-Karp) for efficient comparisons.

Algorithm#

Step 1: Precompute Palindromic Centers

  • Use DP to store palindromic substrings: 
    dp = [[False] * n for _ in range(n)]
for i in range(n):
    dp[i][i] = True  # Single char is palindrome
for i in range(n-1):
    dp[i][i+1] = (s[i] == s[i+1])  # Two-char palindromes
for length in range(3, n+1):
    for i in range(n - length + 1):
        j = i + length - 1
        dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]

Step 2: Rolling Hash Setup

  • Precompute hash and reverse-hash arrays using polynomial rolling hash: 
    base, mod = 131, 10**9+7
hash_arr = [0] * (n + 1)
rev_hash_arr = [0] * (n + 1)
pow_base = [1] * (n + 1)
# Precompute powers
for i in range(1, n + 1):
    pow_base[i] = (pow_base[i-1] * base) % mod
# Prefix hashes
for i in range(n):
    hash_arr[i+1] = (hash_arr[i] * base + ord(s[i])) % mod
# Reverse prefix hashes
for i in range(n - 1, -1, -1):
    rev_hash_arr[n - i] = (rev_hash_arr[n - i - 1] * base + ord(s[i])) % mod

Step 3: Two-Pointer Enumeration

  • Fix s2 (the center palindrome), then enumerate all valid non-overlapping positions for s1 and s3: 
    count = 0
for j_start in range(n):       # Start of s2
    for j_end in range(j_start, n):  # End of s2
        if not dp[j_start][j_end]:   # Skip if s2 not palindrome
            continue
        len_s2 = j_end - j_start + 1
        # s1 must end at or before j_start, s3 must start at or after j_end + 1
        for i_end in range(j_start - 1, -1, -1):  # End position of s1
            len_s1 = j_start - i_end
            for k_start in range(j_end + 1, n + 1):  # Start position of s3
                len_s3 = k_start - j_end - 1
                if len_s1 != len_s3:
                    continue
                s1 = s[i_end - len_s1 + 1:i_end + 1]
                s3 = s[k_start:k_start + len_s3]
                # Compare hash of s1 and reverse(s3)
                hash_s1 = get_hash(hash_arr, i_end - len_s1 + 1, i_end)
                hash_rev_s3 = get_rev_hash(rev_hash_arr, n, k_start + len_s3 - 1, len_s3)
                if hash_s1 == hash_rev_s3:
                    count += 1
return count

Key Optimizations:

  • Early Termination: Skip invalid len_s3.
  • Hashing: ( O(1) ) substring comparison.
  • DP Table: ( O(1) ) palindrome checks for s2.

5. Complexity Analysis#

  • Precomputation:
    • DP Table: ( O(n^2) )
    • Rolling Hash Setup: ( O(n) )
  • Main Loop:
    • Iterating over j_start, j_end: ( O(n^2) )
    • Iterating over len_s1: ( O(n) ) per (j_start, j_end) pair
    • Total Time: ( O(n^3) )
  • Space Complexity: ( O(n^2) ) (DP table) + ( O(n) ) (hash arrays) = ( O(n^2) ).

6. Step-by-Step Example#

Input: s = "abcbab"

Solution:

  1. Precompute Palindromes:

    • dp[2][3] = True ("cb" is not a palindrome; actually "bcb" is. Let's correct: For "abcba", dp[1][3] = True for "bcb").

  2. Fix s2 = "bcb" (positions 1-3):

    • Available space: len_s1_max=1, len_s3_max=1
    • Try len_s1=1: s1 = s[0:1]="a", s3 = s[4:5]="b"
    • Check: reverse(s3) = reverse("b") = "b" ≠ "a" → skip.

  3. Fix s2 = "a" (position 0):

    • s1 must be empty (invalid).

  4. Fix s2 = "bab" (positions 3-5):

    • s1="abc" (positions 0-2), s3 has no space (invalid).

  5. Fix s2 = "c" (position 2):

    • len_s1_max=2, len_s3_max=3
    • Try len_s1=1: s1="a", s3="b" → "a" + "c" + "b" = "acb" (not palindrome).
    • Try len_s1=2: s1="ab", s3="ba" → "ab" + "c" + "ba" = "abcba" (palindrome ✅).

Output: 1 valid triplet.

7. Best Practices and Common Pitfalls#

Best Practices#

  • Rolling Hash: Use double hashing to avoid collisions.
  • DP for Palindromes: Precompute for ( O(1) ) checks.
  • Boundary Checks: Validate substring positions.
  • Module Operations: Prevent integer overflow.

Common Pitfalls#

  • Hash Collisions: Test hash equivalence with direct string comparison.
  • Off-by-One Errors: Double-check loop ranges.
  • Ignoring Constraints: Brute-force fails for ( n \gt 50 ).
  • Overlapping: Ensure ( i + a \leq j ) and ( j + b \leq k ).

8. Conclusion#

Finding three non-overlapping substrings forming a palindrome combines palindromic properties, efficient hashing, and careful boundary handling. The ( O(n^3) ) approach using DP and rolling hash is optimal for ( n \leq 200 ). Real-world variants might involve larger inputs or variable-length substrings—requencing suffix automata or Manacher's algorithm for further optimization.

9. References#

  1. Rabin-Karp Algorithm (Rolling Hash)
  2. Dynamic Programming for Palindromic Substrings
  3. LeetCode Problem: Count of Three Non-Overlapping Substrings as Palindromic Concatenation
  4. Double Hashing for String Collision