8
\$\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\$
6
  • \$\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
  • 1
    \$\begingroup\$ I have posted your review as community wiki (so I don't get credit for your work): it is definitely a brief review, not merely a link. If you post in your own name, we can delete my answer. \$\endgroup\$
    – dcorking
    Nov 18 '17 at 9:01
6
\$\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\$
4
\$\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\$
1
  • \$\begingroup\$ except to put it in the result set afterwards not even that, if not to avoid the object alias. \$\endgroup\$
    – greybeard
    Sep 19 '20 at 9:25
4
\$\begingroup\$

You should also take into consideration the JS methods when calculating time and space complexity. It's not as simple as \$O(n^2)\$ time because you used two nested for loops. Slice, Split, reverse, join are all also \$O(n)\$ operations under the hood. Split also creates a brand new array so that is also \$O(n)\$ space.

\$\endgroup\$
2
\$\begingroup\$

I would say this looks a lot better in performance

function isPalindrome(str){
    let isOk = true;
    for(let i=0; i < str.length/2 ; i++){
        if(str[i] !== str[str.length - i -1]){ isOk = false; break;}
    }
    return isOk;
}


function generateAllPossibleSubstring(str = ''){
    let result =  new Set([]);
        for (let i = 0; i < str.length; i++) {
            for (let j = i + 1; j <= str.length; j++) {
                let sub = str.substring(i, j);
                if(!result.has(sub) && isPalindrome(sub)) result.add(sub);
            }
        }
    return result;
    }


let res = generateAllPossibleSubstring('aabaa');
console.log(res);

The isPalindrome function complexity is N/2 which is faster because we are not reversing then reconstructing the string by joining and then comparing the 2 strings.

Where as generateAllPossibleSubstring is skipping all the unnecessary iteration in your original code by generating only the possible substring of the given string. For lookup i am using set instead of includes function because set is much more faster and has constant lookup complexity.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Welcome to CodeReview@SE. I think your point valid, but found it addressed in RoToRa's '17 answer. \$\endgroup\$
    – greybeard
    Sep 19 '20 at 9:36
  • 1
    \$\begingroup\$ (Something untoward happened to the indentation of your generateAllPossibleSubstring().) \$\endgroup\$
    – greybeard
    Sep 19 '20 at 9:39
  • 1
    \$\begingroup\$ You redundantly check every substring for previous inclusion in result: this deserves a code comment. (While I'm at it: Don't write, never present undocumented/uncommented code.) \$\endgroup\$
    – greybeard
    Sep 19 '20 at 9:42
  • \$\begingroup\$ Thanks for the feedback , can you please update my answer so that i could get a better understanding ? \$\endgroup\$ Sep 19 '20 at 17:17
  • \$\begingroup\$ I'd be more or less glad to if you convert your answer to a (historically named) community wiki post. \$\endgroup\$
    – greybeard
    Sep 20 '20 at 7:37
0
\$\begingroup\$

Originally posted by user Juvian:

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

Both Manacher 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\$
0

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.