-
Notifications
You must be signed in to change notification settings - Fork 0
/
longest_palindromic_substring.js
64 lines (53 loc) · 2.32 KB
/
longest_palindromic_substring.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// https://www.codewars.com/kata/5dcde0b9fcb0d100349cb5c0
function longest_palindrome (s) {
let arr = s.split('');
for (let i = 0; i <= arr.length; i+=2) {
arr.splice(i, 0, '|');
}
let centerIndex = 0;
let leftIndex = 0;
let rightIndex = 0;
let expansionAtIndex = [0];
for (let i = 0; i < arr.length; i++) {
console.log("functionlongest_palindrome -> expansionAtIndex", expansionAtIndex)
let expansion = 0;
expansionAtIndex[i] = 0;
if (i <= rightIndex) {
let mirrorIndex = 2*centerIndex - rightIndex;
if (mirrorIndex - expansionAtIndex[mirrorIndex] >= leftIndex) {
expansion = expansionAtIndex[mirrorIndex];
expansionAtIndex[i] = expansion;
} else {
expansion = rightIndex - i;
expansionAtIndex[i] = expansion;
}
}
while ((i - expansion >= 0) && (i + expansion < arr.length)) {
if (arr[i - expansion] === arr[i + expansion]) {
if (expansionAtIndex[centerIndex] < expansion) {
centerIndex = i;
leftIndex = i - expansion;
rightIndex = i + expansion;
expansionAtIndex[i] = expansion;
}
expansion ++;
} else break
}
}
return arr.slice(leftIndex, rightIndex+1)
.filter(item => item !== '|')
.join('');
}
// TESTS
// console.log(longest_palindrome('babad') === 'bab');
// console.log(longest_palindrome('madam') === 'madam');
// console.log(longest_palindrome('dde') === 'dd');
// console.log(longest_palindrome('ababbab') === 'babbab');
// console.log(longest_palindrome('abababa') === 'abababa');
// console.log(longest_palindrome('banana') === 'anana');
// console.log(longest_palindrome('abba') === 'abba');
// console.log(longest_palindrome('cbbd') === 'bb');
// console.log(longest_palindrome('zz') === 'zz');
// console.log(longest_palindrome('dddd') === 'dddd');
// console.log(longest_palindrome('') === '');
console.log(longest_palindrome('yytyyffyfftyyyytffyfyfyyftfyfftffttyfyyyfftfffttyftttttftyfttytftytytyfftfftttffffyttytfttttytyyftyftffytfttfftfyytyytftttfffffyyyfyttyffyytttftftftfftyfyyytftyyffyffytyttytyytyyffffytfttyyyffttytttyfyyyffyffftyyyfttttyfyytyyfytyfttffyytyffftttfftffyftttyftffyfffyttttfyyffyffyfytffttttfyftfyyyfftfyttfffttyyttfytfffftyyfttytfttyfyfyfftfytffffttfytyfttyttyytttftyfyyyyyfyytytyttftfyftfttty') === 'ttyytyytt');