6
\$\begingroup\$

I've written a function to calculate all the distinct substrings of a given string, that are palindromes. The string is passed as the argument to the function. For example, the string abba is a palindrome because reversed it is also abba. If the function takes the string aabaa it returns 5, because the distinct substrings are a, aa, aabaa, aba, b.

I've currently made use of two for loops for this to work, however, when the string gets big, it's very inefficient due to the fact it iterates one by one. Any suggestions as to how I can make this significantly more efficient? Recursion maybe?

The function:

function countPalindromesInString(s) {

    let subStrings = [];

    for (let i = 0; i < s.length; i++) {
      for(let j = 0; j < s.length - i; j++) {
        let subString = s.substring(j, j + i + 1);
        if(subString === subString.split('').reverse().join('') && !subStrings.includes(subString)) {
          subStrings.push(subString);
        }
      }
    }
    return subStrings.length;
}
\$\endgroup\$
  • \$\begingroup\$ Is the full string guaranteed to be a palindrome? \$\endgroup\$ – Gerrit0 Nov 13 '17 at 4:59
  • \$\begingroup\$ @Gerrit0 yes the initial input is a palindrome. \$\endgroup\$ – Matt Kent Nov 13 '17 at 9:26
  • 2
    \$\begingroup\$ This can be solved in O(n) either with Manchester or palindromic tree : adilet.org/blog/25-09-14 \$\endgroup\$ – juvian Nov 13 '17 at 16:16
  • \$\begingroup\$ @juvian Better to post a short answer than review the code in comments, which are temporary. \$\endgroup\$ – dcorking Nov 17 '17 at 8:50
  • \$\begingroup\$ @dcorking well, answers were already given and seeing it accepted would suggest that efficient wise its already enough. Both manchester and palindromic tree are a bit harder to implement and definitely not easy to understand, so as long as performance is not needed its good to avoid them. Besides, meta.stackexchange.com/questions/8231/… \$\endgroup\$ – juvian Nov 17 '17 at 16:42
4
\$\begingroup\$

You code looks pretty neat, i do not think that using recursion would improve it very much, but i have some minor suggestions;

1) Performance-wise improvements

The only thing that seems odd at first glance is how you reverse the string to compare subString.split('').reverse().join('');

I had to look it up, but i found that the way that you are doing its the right way using In-built functions, and its pretty much good for almost all cases, but if you want to improve a little the performance you could use something like:

function reverse(s) {
  var o = [];
  for (var i = 0, len = s.length; i <= len; i++)
    o.push(s.charAt(len - i));
   return o.join('');
}

Using this function is has an improve in performance over your current implementation.

2) Readability

You could extract your conditional and use it as a function so your intent would be more clear:

let isPalindrome = function (word, words) {
  return word === word.split('').reverse().join('') && !words.includes(word)
}

and use this function in the conditional as:

if(isPalisdrome(subString, subStrings)) {
          subStrings.push(subString);
 }

3) Conclusion

In the end putting all together the code would be something like:

function reverse(s) {
  var o = [];
  for (var i = 0, len = s.length; i <= len; i++)
   o.push(s.charAt(len - i));
   return o.join('');
}

function isPalindrome(word, words) {
  return word === reverse(word) && !words.includes(word)
}

function countPalindromesInString(s) {
    let subStrings = [];
    for (let i = 0; i < s.length; i++) {
      for(let j = 0; j < s.length - i; j++) {
        let subString = s.substring(j, j + i + 1);
        if(isPalindrome(subString, subStrings)) {
          subStrings.push(subString);
        }
    }
  }
  return subStrings.length;
}
\$\endgroup\$
2
\$\begingroup\$

Checking for a duplicate in the results array is one slow point. It adds one level of complexity because each contains call has to loop over the whole list. Instead use a Set (if you can use ECMAScript 6) or store the strings as a key in an object (this however requires counting the keys at the end which can be a bit bothersome unless you can use Object.keys() which in turn requires ECMAScript 5.1):

var resultSet = {};

// ... inside the loop if the substring is a palindrome
resultSet[substring] = true;

var count = 0;
for (key in resultSet) {
   if (resultSet.hasOwnProperty(key)) count++;
}
return count;

(I just realized you are using let so you can use Set, too. I'm just leaving this in, in case it interests someone else.)


There is no reason to actually create the reverse string in order to check for a palindrome. Instead simply loop over the first half of the string and compare the nth character with the (length - n - 1)th character.

function isPalindrom(str) {
  var len = str.length;
  var half = Math.floor(len / 2);
  for (var i = 0; i < half; i++) {
    if (str.charAt(i) !== str.charAt(len - i - 1)) {
      return false;
    }
  }
  return true;
}

This even could be taken one more step: There is no reason to create the substring for the palindrome detection, except to put it in the result set afterwards.

function isPalindrom(str, from, to) {
  let len = from - to + 1;
  let half = Math.floor(len / 2);
  let end = from + half + 1;
  for (var i = from; i < end; i++) {
    if (str.charAt(i) !== str.charAt(len - i - 1)) {
      return false;
    }
  }
  return true;
}

function countPalindromesInString(s) {

    let subStrings = new Set();

    for (let i = 0; i < s.length; i++) {
      for (let j = 0; j < s.length - i; j++) {
        let end = j + i + 1;
        if (isPalindrom(s, j, end)) {
          subStrings.push(s.substring(j, end));
        }
      }
    }

    return subStrings.size;
}
\$\endgroup\$
0
\$\begingroup\$

Originally posted by user Juvian:

This can be solved in O(n) either with Manchester or palindromic tree : adilet.org/blog/25-09-14

Both manchester and palindromic tree are a bit harder to implement and definitely not easy to understand, so as long as performance is not needed its good to avoid them.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.