Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2484.html

2484. Count Palindromic Subsequences

  • Difficulty: Hard.
  • Related Topics: String, Dynamic Programming.
  • Similar Questions: Arithmetic Slices II - Subsequence, Count Different Palindromic Subsequences, Unique Length-3 Palindromic Subsequences.

Problem

Given a string of digits s, return the number of **palindromic subsequences of** s** having length 5. Since the answer may be very large, return it **modulo 109 + 7.

Note:

  • A string is palindromic if it reads the same forward and backward.

  • A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

  Example 1:

Input: s = "103301"
Output: 2
Explanation: 
There are 6 possible subsequences of length 5: "10330","10331","10301","10301","13301","03301". 
Two of them (both equal to "10301") are palindromic.

Example 2:

Input: s = "0000000"
Output: 21
Explanation: All 21 subsequences are "00000", which is palindromic.

Example 3:

Input: s = "9999900000"
Output: 2
Explanation: The only two palindromic subsequences are "99999" and "00000".

  Constraints:

  • 1 <= s.length <= 104

  • s consists of digits.

Solution (Java, C++, Python)

  • class Solution {
        private static final int MOD = (int) 1e9 + 7;
    
        public int countPalindromes(String s) {
            int n = s.length();
            int[][][] pre = new int[n + 2][10][10];
            int[][][] suf = new int[n + 2][10][10];
            int[] t = new int[n];
            for (int i = 0; i < n; ++i) {
                t[i] = s.charAt(i) - '0';
            }
            int[] c = new int[10];
            for (int i = 1; i <= n; ++i) {
                int v = t[i - 1];
                for (int j = 0; j < 10; ++j) {
                    for (int k = 0; k < 10; ++k) {
                        pre[i][j][k] = pre[i - 1][j][k];
                    }
                }
                for (int j = 0; j < 10; ++j) {
                    pre[i][j][v] += c[j];
                }
                c[v]++;
            }
            c = new int[10];
            for (int i = n; i > 0; --i) {
                int v = t[i - 1];
                for (int j = 0; j < 10; ++j) {
                    for (int k = 0; k < 10; ++k) {
                        suf[i][j][k] = suf[i + 1][j][k];
                    }
                }
                for (int j = 0; j < 10; ++j) {
                    suf[i][j][v] += c[j];
                }
                c[v]++;
            }
            long ans = 0;
            for (int i = 1; i <= n; ++i) {
                for (int j = 0; j < 10; ++j) {
                    for (int k = 0; k < 10; ++k) {
                        ans += (long) pre[i - 1][j][k] * suf[i + 1][j][k];
                        ans %= MOD;
                    }
                }
            }
            return (int) ans;
        }
    }
    
  • class Solution {
    public:
        const int mod = 1e9 + 7;
    
        int countPalindromes(string s) {
            int n = s.size();
            int pre[n + 2][10][10];
            int suf[n + 2][10][10];
            memset(pre, 0, sizeof pre);
            memset(suf, 0, sizeof suf);
            int t[n];
            for (int i = 0; i < n; ++i) t[i] = s[i] - '0';
            int c[10] = {0};
            for (int i = 1; i <= n; ++i) {
                int v = t[i - 1];
                for (int j = 0; j < 10; ++j) {
                    for (int k = 0; k < 10; ++k) {
                        pre[i][j][k] = pre[i - 1][j][k];
                    }
                }
                for (int j = 0; j < 10; ++j) {
                    pre[i][j][v] += c[j];
                }
                c[v]++;
            }
            memset(c, 0, sizeof c);
            for (int i = n; i > 0; --i) {
                int v = t[i - 1];
                for (int j = 0; j < 10; ++j) {
                    for (int k = 0; k < 10; ++k) {
                        suf[i][j][k] = suf[i + 1][j][k];
                    }
                }
                for (int j = 0; j < 10; ++j) {
                    suf[i][j][v] += c[j];
                }
                c[v]++;
            }
            long ans = 0;
            for (int i = 1; i <= n; ++i) {
                for (int j = 0; j < 10; ++j) {
                    for (int k = 0; k < 10; ++k) {
                        ans += 1ll * pre[i - 1][j][k] * suf[i + 1][j][k];
                        ans %= mod;
                    }
                }
            }
            return ans;
        }
    };
    
  • class Solution:
        def countPalindromes(self, s: str) -> int:
            mod = 10**9 + 7
            n = len(s)
            pre = [[[0] * 10 for _ in range(10)] for _ in range(n + 2)]
            suf = [[[0] * 10 for _ in range(10)] for _ in range(n + 2)]
            t = list(map(int, s))
            c = [0] * 10
            for i, v in enumerate(t, 1):
                for j in range(10):
                    for k in range(10):
                        pre[i][j][k] = pre[i - 1][j][k]
                for j in range(10):
                    pre[i][j][v] += c[j]
                c[v] += 1
            c = [0] * 10
            for i in range(n, 0, -1):
                v = t[i - 1]
                for j in range(10):
                    for k in range(10):
                        suf[i][j][k] = suf[i + 1][j][k]
                for j in range(10):
                    suf[i][j][v] += c[j]
                c[v] += 1
            ans = 0
            for i in range(1, n + 1):
                for j in range(10):
                    for k in range(10):
                        ans += pre[i - 1][j][k] * suf[i + 1][j][k]
                        ans %= mod
            return ans
    
    
  • func countPalindromes(s string) int {
    	n := len(s)
    	pre := [10010][10][10]int{}
    	suf := [10010][10][10]int{}
    	t := make([]int, n)
    	for i, c := range s {
    		t[i] = int(c - '0')
    	}
    	c := [10]int{}
    	for i := 1; i <= n; i++ {
    		v := t[i-1]
    		for j := 0; j < 10; j++ {
    			for k := 0; k < 10; k++ {
    				pre[i][j][k] = pre[i-1][j][k]
    			}
    		}
    		for j := 0; j < 10; j++ {
    			pre[i][j][v] += c[j]
    		}
    		c[v]++
    	}
    	c = [10]int{}
    	for i := n; i > 0; i-- {
    		v := t[i-1]
    		for j := 0; j < 10; j++ {
    			for k := 0; k < 10; k++ {
    				suf[i][j][k] = suf[i+1][j][k]
    			}
    		}
    		for j := 0; j < 10; j++ {
    			suf[i][j][v] += c[j]
    		}
    		c[v]++
    	}
    	ans := 0
    	const mod int = 1e9 + 7
    	for i := 1; i <= n; i++ {
    		for j := 0; j < 10; j++ {
    			for k := 0; k < 10; k++ {
    				ans += pre[i-1][j][k] * suf[i+1][j][k]
    				ans %= mod
    			}
    		}
    	}
    	return ans
    }
    

Explain:

nope.

Complexity:

  • Time complexity : O(n).
  • Space complexity : O(n).

All Problems

All Solutions