2
\$\begingroup\$

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.

  1. cacbbba (3 palindromes)
  2. acbbbac (3 palindromes)
  3. cbbbaca (3 palindromes)
  4. bbbacac (3 palindromes)
  5. bbacacb (3 palindromes)
  6. bacacbb (3 palindromes)
  7. acacbbb (3 palindromes)

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

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

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

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

                if (sub.length < 2) continue;

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

        return max;
    };

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

    return result;
}
console.log(circularPalindromes('cacbbba'));

\$\endgroup\$
1
\$\begingroup\$

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 < s.length; i++) {
        currentLength = 1;
        j1 = (i < 1) ? length2 : i - 1;
        j2 = (i >= length2) ? 0 : i + 1;

        while (s[i] === s[j2] && currentLength < length) {
            currentLength++;
            if (++j2 >= length) j2 = 0;
        }
        equalsLength = currentLength;

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

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

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

    return largest;
}

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

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

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

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

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

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

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

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

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

console.log(circularPalindromes('cacbbba'));
\$\endgroup\$
  • \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and why it is better than the original) so that the author and other readers can learn from your thought process. \$\endgroup\$ – Martin R Nov 22 '18 at 12:28
  • \$\begingroup\$ I'll go back and add some explanation; however, I did explain why it's better than the original, and even attached a performance test. Also, I am the author :) \$\endgroup\$ – AnonymousSB Nov 22 '18 at 20:56

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.