# 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.

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'));

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'));

• 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. – Martin R Nov 22 '18 at 12:28
• 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 :) – AnonymousSB Nov 22 '18 at 20:56