Find palindromes in circular rotated string I'm trying to tackle a programming challenge to determine how many palindromes exist in a given string that is being rotated character by character. My solution works, but it's too slow, and I'm struggling on where to optimize it.

For example, the string "cacbbba" would rotate 6 times, and would have 3 palindromes in each string.


cacbbba (3 palindromes)
acbbbac (3 palindromes)
cbbbaca (3 palindromes)
bbbacac (3 palindromes)
bbacacb (3 palindromes)
bacacbb (3 palindromes)
acacbbb (3 palindromes)




function circularPalindromes(s) {
    const k = s.length;
    const result = [];
    const isPalindrome = (str) =&gt; {
        const len = str.length;

        for (let i = 0; i &lt; len / 2; i++) {
            if (str[i] !== str[len - 1 - i]) {
                return false;
            }
        }

        return true;
    };
    const subs = (s) =&gt; {
        let max = 0;

        for (let i = 0; i &lt; s.length; i++) {
            for (let j = 1; j &lt;= s.length - i; j++) {
                const sub = s.substring(i, i + j);

                if (sub.length &lt; 2) continue;

                if (isPalindrome(sub) &amp;&amp; sub.length &gt; max) {
                    max = sub.length;
                }
            }
        }

        return max;
    };

    for (let i = 0; i &lt; k; i++) {
        result.push(subs(s.substring(i, k) + s.substring(0, i)));
    }

    return result;
}
console.log(circularPalindromes('cacbbba'));
After trying to optimize my current solution and getting nowhere fast, I went back to the drawing board and came up with this solution. The performance gains are outstanding: 543,334 ops per/sec vs. 275 ops per/sec

Performance Test

https://jsperf.com/largest-vs-subs

Solution

function circularPalindromes(s) {
    s = s.split('');

    let currentLength, equalsLength, j1, j2;
    const length = s.length;
    const length2 = s.length - 1;
    const largest = new Array(s.length).fill(0);

    for (let i = 0; i &lt; s.length; i++) {
        currentLength = 1;
        j1 = (i &lt; 1) ? length2 : i - 1;
        j2 = (i &gt;= length2) ? 0 : i + 1;

        while (s[i] === s[j2] &amp;&amp; currentLength &lt; length) {
            currentLength++;
            if (++j2 &gt;= length) j2 = 0;
        }
        equalsLength = currentLength;

        if (currentLength &gt; 1) {
            checkEqual(largest, i, currentLength);
            i += currentLength - 1;
        }

        while (s[j1] === s[j2] &amp;&amp; currentLength &lt; length &amp;&amp; j1 !== j2) {
            currentLength += 2;
            if (--j1 &lt; 0) j1 = length2;
            if (++j2 &gt;= length) j2 = 0;
        }

        if (currentLength &gt; equalsLength) {
            if(++j1 &gt;= length) j1 = 0;
            checkLargest(largest, j1, currentLength, equalsLength);
        }
    }

    return largest;
}

function checkEqual(largest, position, length) {
    const limit = position + length;
    const middle = position + (length &gt;&gt; 1);
    const even = (length &amp; 1) === 0;

    for (let i = (position - largest.length + length &lt; 0 ? 0 : position - largest.length + length); i &lt; position; i++) {
        if (largest[i] &lt; length)  largest[i] = length;
    }

    for (let i = position + length; i &lt; largest.length; i++) {
        if (largest[i] &lt; length) largest[i] = length;
    }

    for (let i = position, j = position; i &lt; limit; i++, j++) {
        if (j &gt;= largest.length) j = i % largest.length;
        if (largest[j] &lt; length) largest[j] = length;
        if (i &lt; middle){
            length--;
        } else if (i &gt; middle) {
            length++;
        } else if (even) {
            length++;
        }
    }
}

function checkLargest(largest, position, length, equalsLength) {
    const limit1 = position + (length &gt;&gt; 1) - (equalsLength &gt;&gt; 1);
    const limit2 = position + length;

    for (let i = (position - largest.length + length &lt; 0 ? 0 : position - largest.length + length); i &lt; position; i++) {
        if (largest[i] &lt; length) largest[i] = length;
    }

    for (let i = position + length; i &lt; largest.length; i++) {
        if (largest[i] &lt; length)  largest[i] = length;
    }

    for (let i = position, j = position; i &lt; limit1; i++, j++) {
        if (j &gt;= largest.length) j = i % largest.length;
        if (largest[j] &lt; length) largest[j] = length;
        length -= 2;
    }

    for (let i = limit1 + equalsLength, j = limit1 + equalsLength; i &lt; limit2; i++, j++) {
        if (j &gt;= largest.length) j = i % largest.length;
        if (largest[j] &lt; length) largest[j] = length;
        length += 2;
    }
}

console.log(circularPalindromes('cacbbba'));