LeetCode Meditations: Palindromic Substrings

The description for Palindromic Substrings is:

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

For example:

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Or:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Also, the constraints indicate that s consists of lowercase English letters.

---

In the previous problem, we found a solution to find the longest palindromic substring in a given string. To find a palindrome, we used an "expand over center" approach, where we assumed each character as the middle character of a substring. And, accordingly, we shifted the left and right pointers.

Note

Checking a palindrome is easy with two pointers approach, which we've seen before with Valid Palindrome.

Counting the palindromes in one substring may look like this:

function countPalindromesInSubstr(s: string, left: number, right: number): number {
  let result = 0;
  while (left >= 0 && right 



<p>As long as we're within bounds (left >= 0 && right 

</p><p>However, once you think about it, it matters which indices the pointers are initialized at. For example, if we pass the string "abc" to countPalindromesInSubstr, and the left pointer is at 0 while the right pointer is at the last index (2), then our result is simply 0.</p>

<p>Remember that we are assuming each character as the middle character of a substring, and since each single character is also a substring as well, we'll initialize our left and right pointers to point to the character itself.</p>

<div class="table-wrapper-paragraph"><table>
<thead>
<tr>
<th>Note</th>
</tr>
</thead>
<tbody>
<tr>
<td>A character by itself is considered palindromic, i.e., "abc" has three palindromic substrings: 'a', 'b' and 'c'.</td>
</tr>
</tbody>
</table></div>


<hr>

<p>Let's see how this process might look like.</p>

<p>If we have the string "abc", we'll first assume that 'a' is the middle of a substring:<br>
</p>

<pre class="brush:php;toolbar:false">"abc"

left = 0
right = 0
currentSubstr = 'a'

totalPalindromes = 1 // A single character is a palindrome

Then, we'll try to expand the substring to see if 'a' can be the middle character of another substring:

"abc"

left = -1
right = 1
currentSubstr = undefined

totalPalindromes = 1

Now that our left pointer is out of bounds, we can jump to the next character:

"abc"

left = 1
right = 1
currentSubstr = 'b'

totalPalindromes = 2

Now, we'll update our pointers, and indeed, 'b' can be the middle character of another substring:

s = "abc"

left = 0
right = 2
currentSubstr = 'abc'

totalPalindromes = 2

Well, currentSubstr is not a palindrome. Now we update our pointers again:

s = "abc"

left = -1
right = 3
currentSubstr = undefined

totalPalindromes = 2

And, we're out of bounds again. Time to move on to the next character:

s = "abc"

left = 2
right = 2
currentSubstr = 'c'

totalPalindromes = 3

Shifting our pointers, we'll be out of bounds again:

s = "abc"

left = 1
right = 3
currentSubstr = undefined

totalPalindromes = 3

Now that we've gone through each character, our final result of totalPalindromes is, in this case, 3. Meaning that there are 3 palindromic substrings in "abc".

However, there is an important caveat: each time we assume a character as the middle and initialize two pointers to the left and right of it, we're trying to find only odd-length palindromes. In order to mitigate that, instead of considering a single character as the middle, we can consider two characters as the middle and expand as we did before.

In this case, the process of finding the even-length substring palindromes will look like this — initially, our right pointer is left + 1:

s = "abc"

left = 0
right = 1
currentSubstr = 'ab'

totalPalindromes = 0

Then, we'll update our pointers:

s = "abc"

left = -1
right = 2
currentSubstr = undefined

totalPalindromes = 0

Out of bounds. On to the next character:

s = "abc"

left = 1
right = 2
currentSubstr = 'bc'

totalPalindromes = 0

Updating our pointers:

s = "abc"

left = 0
right = 3
currentSubstr = undefined

totalPalindromes = 0

The right pointer is out of bounds, so we go on to the next character:

s = "abc"

left = 2
right = 3
currentSubstr = undefined

totalPalindromes = 0

Once again we're out of bounds, and we're done going through each character. There are no palindromes for even-length substrings in this example.

---

We can write a function that does the work of counting the palindromes in each substring:

function countPalindromes(s: string, isOddLength: boolean): number {
  let result = 0;
  for (let i = 0; i 



<p>In our main function, we can call countPalindromes twice for both odd and even length substrings, and return the result:<br>
</p>

<pre class="brush:php;toolbar:false">function countSubstrings(s: string): number {
  let result = 0;
  result += countPalindromes(s, true); // Odd-length palindromes
  result += countPalindromes(s, false); // Even-length palindromes

  return result;
}

Overall, our solution looks like this:

function countSubstrings(s: string): number {
  let result = 0;
  result += countPalindromes(s, true); // Odd-length palindromes
  result += countPalindromes(s, false); // Even-length palindromes

  return result;
}

function countPalindromes(s: string, isOddLength: boolean): number {
  let result = 0;
  for (let i = 0; i = 0 && right 



<h4>
  
  
  Time and space complexity
</h4>

<p>The time complexity is <link rel="stylesheet" href="https://dev.to/assets/katex-e2c941bc70d758b1651b592985b41c97281f578aa1cd647c66152eebf4fe0a69.css">


  <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>2</mn></msup><mo stretchy="false">)</mo></mrow>O(n^2) </semantics></math><span class="base"><span class="strut" style="height:1.0641em;vertical-align:-0.25em;">O(<span class="mord mathnormal">n<span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"><span class="mord mtight">2</span></span></span></span></span></span></span>)</span></span></span>
</span>
 as we go through each substring for each character (countPalindromes is doing an 

  <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>2</mn></msup><mo stretchy="false">)</mo></mrow>O(n^2) </semantics></math><span class="base"><span class="strut" style="height:1.0641em;vertical-align:-0.25em;">O(<span class="mord mathnormal">n<span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"><span class="mord mtight">2</span></span></span></span></span></span></span>)</span></span></span>
</span>
 operation, we call it twice <em>separately</em>.)<br>
The space complexity is 

  <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow>O(1) </semantics></math><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;">O(1)</span></span></span>
</span>
 as we don't have an additional data structure whose size will grow with the input size.</p>


<hr>

<p>Next up is the problem called Decode Ways. Until then, happy coding.</p>


          

            
  

            
        

The above is the detailed content of LeetCode Meditations: Palindromic Substrings. For more information, please follow other related articles on the PHP Chinese website!