1+ class PalindromicSubstringsCounter {
2+
3+ /**
4+ * Generates boundary conditions using a quadratic loop. For each boundary condition, validates if the subtring
5+ * is a valid palindrome using an O(n) operation.
6+ *
7+ * Time: O(n^3) since nested 3 levels iteration is happening.
8+ * Space: O(1) no additional space is used.
9+ *
10+ * @param input
11+ */
12+ countBF ( input : string ) {
13+
14+ let total = 0 ;
15+
16+ // Create a range of boundary conditions which is used for a possible substring
17+ for ( let beg = 0 ; beg < input . length ; beg ++ ) {
18+ for ( let end = beg ; end < input . length ; end ++ ) {
19+ total += this . isValidPalindrome ( input , beg , end ) ? 1 : 0 ;
20+ }
21+ }
22+
23+ return total ;
24+ }
25+
26+ /**
27+ * Brute force recursive operation to compute the count. We start with the 2 extremes and take 3 directions at each step. 1 direction is to
28+ * identify if the current string is a valid palindrome. We do this by recursively computing the state of the substring inside. The other 2
29+ * cases include: Taking the substring getting rid of the 1st element and taking the substring getting rid of the last element.
30+ *
31+ * Time: O(3^n) since we are taking 3 directions for each possible input character range.
32+ * Space: O(n) + O(n) for the recursion depth and the storage of the total palindrome found.
33+ *
34+ * @param input
35+ */
36+ countBFRecursive ( input : string ) {
37+
38+ const result : Set < string > = new Set ( ) ;
39+
40+ function countHelper ( input : string , beg : number , end : number ) {
41+
42+ // Base Conditions where the palindrome is valid
43+ if ( end < beg ) return true ;
44+ if ( end == beg ) {
45+ result . add ( `${ beg } ${ end } ) ;
46+ return true ;
47+ }
48+
49+ countHelper ( input , beg , end - 1 )
50+ countHelper ( input , beg + 1 , end )
51+
52+ // Case: checking if the strings are palindrome using extremes matching and recursive substring.
53+ if ( input [ beg ] === input [ end ] && countHelper ( input , beg + 1 , end - 1 ) ) {
54+ result . add ( `${ beg } ${ end } ) ;
55+ return true ;
56+ } else {
57+ return false ;
58+ }
59+ }
60+
61+ countHelper ( input , 0 , input . length - 1 ) ;
62+ // console.log(result)
63+
64+ return result . size ;
65+ }
66+
67+ countDPBottomsUp ( input : string ) {
68+
69+ // Create a DP table defining the number of valid palindromic strings for the substrings starting at (row) and ending at (col).
70+ const dp : number [ ] [ ] = Array . from ( { length : input . length + 1 } , ( ) => Array ( input . length ) . fill ( 0 ) ) ;
71+
72+ // Init boundary conditions (for each substring starting and ending at the idx position, there is only 1 valid palindrome.)
73+ for ( let idx = 0 ; idx < input . length ; idx ++ ) dp [ idx ] [ idx ] = 1 ;
74+
75+ /** a b c d
76+ * a [1 2 3 4
77+ * b 5 6 2]
78+ * c 4 1
79+ */
80+
81+ // Build the solution for all character range. DP row represents the starting char and col represents the ending char.
82+ for ( let beg = input . length ; beg >= 0 ; beg -- ) {
83+ for ( let end = beg + 1 ; end < input . length ; end ++ ) {
84+
85+ // Case 1: If the extremes are matching
86+ // If the substring at beg + 1:end - 1 are matching, we update 1 to the counter.
87+ // If the susbtrings are not matching, we dont have a palindrome, take the last one.
88+ if ( input [ beg ] === input [ end ] ) {
89+ dp [ beg ] [ end ] = dp [ beg + 1 ] [ end - 1 ] ;
90+ }
91+
92+ dp [ beg ] [ end ] += dp [ beg + 1 ] [ end ] ;
93+ }
94+ }
95+
96+ return dp [ 0 ] [ input . length - 1 ] ;
97+ }
98+
99+ /**
100+ * Returns true if the input string with boundary conditions is a valid palindrome.
101+ * @param input
102+ * @param beg
103+ * @param end
104+ */
105+ isValidPalindrome ( input : string , beg : number , end : number ) {
106+ while ( end >= beg ) {
107+ if ( input [ end -- ] !== input [ beg ++ ] ) return false ;
108+ }
109+
110+ return true ;
111+ }
112+ }
113+
114+ function testCountPalindromeSubstring ( input : string ) {
115+ const counter = new PalindromicSubstringsCounter ( ) ;
116+ console . log ( `Counter BF for input: ${ input } ${ counter . countBF ( input ) } ) ;
117+ console . log ( `Counter BF Recursive for input: ${ input } ${ counter . countBFRecursive ( input ) } )
118+ // console.log(`Counter DP bottoms up for input: ${input} returned for ${counter.countDPBottomsUp(input)}`);
119+ }
120+
121+ testCountPalindromeSubstring ( "abdbca" )
122+ testCountPalindromeSubstring ( "cddpd" )
123+ testCountPalindromeSubstring ( "pqr" )
0 commit comments