/**
* @param {string} s
* @return {number}
*/
// Brute Force Approach
// Add up s.length to count since all substrings of length 1 are palindromes
// Check every start and end position for a substring and verify it is a palindrome
// loop from i to end
//   loop from j starting from i + 1 to end
//     if substring from i to j is a palindrome, 
//       increment the count by 1
// O(n^2) for finding all substring, O(n) to check palindrome
// O(n^3) overall time, O(1) space
var countSubstrings = function(s) {
 const isPalindrome = (start, end) => {
   let left = start;
   let right = end;
   
   while (left < right) {
     if (s[left] !== s[right]) {
       return false;
     }
     left++;
     right--;
   }
   
   return true;
 };
 
 // All substrings of length 1 are a palindrome, so we add it to the count
 let count = s.length; 
 
 // Check every start and end position for a substring
 for (let i = 0; i < s.length; i++) {
   for (let j = i + 1; j < s.length; j++) {
     // If substring from i to j is a palindrome, add to the count
     if (isPalindrome(i, j)) {
       count++;
     }
   }
 }
 
 return count;
};