Count Palindromic Strings with Constraints

Problem Overview

Count palindromic strings of every length from 1 through n that use only distinct letters, drawn from an alphabet of size k.

Intuition

Count palindromic strings of every length from 1 through n that use only distinct letters, drawn from an alphabet of size k. A palindrome is fixed by its first half (and the middle letter when length is odd). Pick m distinct symbols for the mirrored pairs in order: that is P(k, m). For odd length 2m+1, the center must be a new symbol, giving k minus m choices.

Algorithm

1Let perm track P(k, m), starting at 1 for m = 0.
2For m from 0 while 2m <= n and m <= k: update perm when m > 0.
3If 2m+1 <= n, add perm * (k - m) for odd lengths.
4If m > 0 and 2m <= n, add perm for even lengths.
5Return the sum modulo 1e9+7.

Example Walkthrough

Input: n = 3, k = 3

1. m = 0: length 1 palindromes, 3 choices.
2. m = 1: length 2 gives P(3,1) = 3; length 3 gives 3 * 2 = 6.
3. Total 3 + 3 + 6 = 12.

Output: 12

Common Pitfalls

• Stop when m > k. Further terms are zero because you cannot pick m distinct symbols.
• Even length 2m uses perm at m, not perm at m-1.
• The center factor for odd length is (k - m), not k.
• Sum all valid lengths up to n, not only palindromes of length exactly n.

Count Palindromic Strings with Constraints.java

Java

// Approach: Count palindromes of length 1..n whose letters are all distinct,
// chosen from k symbols. Even length 2m uses P(k,m) for the first half; odd
// length 2m+1 multiplies by (k-m) for the center. Sum over valid m.
// Complexity: O(min(n, k)) time and O(1) extra space.

class Solution {

    static final long MOD = 1_000_000_007L;

    public int palindromicStrings(int n, int k) {
        long ans = 0;
        long perm = 1;

        for (int m = 0; 2 * m <= n && m <= k; m++) {
            if (m > 0) {
                perm = perm * (k - m + 1) % MOD;
            }

            if (2 * m + 1 <= n) {
                ans = (ans + perm * (k - m)) % MOD;
            }

            if (m > 0 && 2 * m <= n) {
                ans = (ans + perm) % MOD;
            }
        }

        return (int) ans;
    }
}

Was this solution helpful?