Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Shortest Palindrome
Bookmark
Brute Force
KMP
Rolling Hash
Input
aacecaaa
abcd
aba
abbacd
Custom
s
=
aacecaaa
s
a
0
a
1
c
2
e
3
c
4
a
5
a
6
a
7
k = -
result = ""
s
a
0
a
1
c
2
e
3
c
4
a
5
a
6
a
7
k = -
result = ""
s
a
0
a
1
c
2
e
3
c
4
a
5
a
6
a
7
k = 8
result = ""
is "aacecaaa" a palindrome?
s
a
0
a
1
c
2
e
3
c
4
a
5
a
6
a
7
k = 8
result = ""
s[1] = 'a' vs s[6] = 'a'
s
a
0
a
1
c
2
e
3
c
4
a
5
a
6
a
7
k = 8
result = ""
s[2] = 'c' vs s[5] = 'a'
s
a
0
a
1
c
2
e
3
c
4
a
5
a
6
a
7
k = 8
result = ""
length 8 fails, try one shorter
s
a
0
a
1
c
2
e
3
c
4
a
5
a
6
a
7
k = 7
result = ""
s[0] = 'a' vs s[6] = 'a'
s
a
0
a
1
c
2
e
3
c
4
a
5
a
6
a
7
k = 7
result = ""
s[1] = 'a' vs s[5] = 'a'
s
a
0
a
1
c
2
e
3
c
4
a
5
a
6
a
7
k = 7
result = ""
s[2] = 'c' vs s[4] = 'c'
s
a
0
a
1
c
2
e
3
c
4
a
5
a
6
a
7
k = 7
result = "aaacecaaa"
reverse "a" and put it in front
s
a
0
a
1
c
2
e
3
c
4
a
5
a
6
a
7
k = 7
result = "aaacecaaa"
reverse "a" and put it in front
algo
master
.
io
Step:
Prepend as few characters as possible to make "aacecaaa" a palindrome
0 / 12
Input
aacecaaa
abcd
aba
abbacd
Custom
s
=
aacecaaa
0 / 12
algo
master
.
io
Step:
Prepend as few characters as possible to make "aacecaaa" a palindrome
