111.md

Solution

Submission link - https://bigfrontend.dev/problem/Count-palindromic-substrings/discuss/947

/**
 * @param {string} str
 * @return {number}
 */
function countPalindromicSubstr(str) {

  let count = 0;

  // utility function to check if a given string is palindrome
  function isPalindrome(str) {
    let i = 0;
    let j = str.length-1;
    let mid = Math.floor(str.length/2);

    while(j >= mid) {
      if(str[i] == str[j]) {
        i++;
        j--;
      } else {
        return false;
      }
    }
    return true;
  }

  // loop over each character
  for(let i = 0; i < str.length; i++) {
    // loop over each character but starting with current character from above loop
    for(let j = 1; j <= (str.length - i); j++) {
      if(isPalindrome(str.substr(i, j))) {
        count++;
      }
    }
  }

  return count;

}

Short story

I knew how to check if a given is palindrome or not. It was interesting for me because I at least knew a partial solution. I checked at sample input and output and build my own. It is important to look at sample input and output. It helps you to think and derive a potential solution.

Though the solution is not elegant but happy about the attempt.

Algorithm

• We iterate over each string characters
• We will anchor the current character and proceed with another iteration where the starting index is 1 to pass it to to substr function
• This way we form a substring and we check if the subpart of the string is palindrome or not
• If it is palindrome then we increment the counter

Algorithm - Palindrome

1. We keep two pointers, their values are first and last string characters
2. We move these pointers in their forward (we increment one and we decrement another)
3. We iterate till both the pointers meet a midpoint
4. In each iteration, it will compare characters from these pointers
5. If they match then it will continue else we return false

Code overview

1. We begin by declaring the counter variable. We will increment this when the substring is palindromic
2. We create a utility function isPalindrome whose job to determine if the string is palindrome or not
   1. We declare 2 variables (aka pointers) i and j
   2. We initialize is value with 0 and js value with str.length (two pointers at extreme ends)
   3. We also want to run for-loop till these two pointers meet a middle point. We will declare mid and initialize by str.length / 2 We will use Math.floor to convert into an integer.
   4. At this point, we run a while-loop till j >= mid. We choose this condition because we decrement js value till it reaches mid
   5. If both the pointers have equal string character then we move pointers by incrementing is value and decrementing js value
   6. If the condition is false means the string isn't palindrome and we immediately return false
   7. Otherwise, after the while-loop, we return true
3. We use 2 for-loops to get substring and check if they are palindromic or not
4. We iterate over each character in the first for loop and in each iteration of this for-loop we use another for-loop
5. The job of 2nd for-loop is to anchor the current character from 1st for-loop and iterate over subsequent characters
6. These two for-loops form substrings that we pass to isPalindrome function
7. If we get a true return value then we increment the counter
8. After loop completion we return counter

🌻 ✨

---

I'm excited to improve the solution and code walkthrough. Feel free to drop a comment, or send a PR or send memes @knowkalpesh.