Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Palindrome Partitioning II
Bookmark
Input
Simple
Palindrome heavy
Full palindrome
Mixed
Custom
s
=
aab
s =
"aab"
n =
3
s
a
0
a
1
b
2
cuts
0
0
1
1
2
2
fewest cuts so every piece of "aab" is a palindrome?
s =
"aab"
n =
3
s
a
0
a
1
b
2
cuts
0
0
1
1
2
2
fewest cuts so every piece of "aab" is a palindrome?
s =
"aab"
n =
3
s
a
0
a
1
b
2
cuts
0
0
1
1
2
2
worst case: cut after every char,
cuts[i] = i
s =
"aab"
n =
3
s
a
0
a
1
b
2
center 0
cuts
0
0
1
1
2
2
"a"
is a palindrome (s[0..0])
s =
"aab"
n =
3
s
a
0
a
1
b
2
center 0
cuts
0
0
1
1
2
2
the whole prefix is a palindrome:
cuts[0]
=
0
s =
"aab"
n =
3
s
a
0
a
1
b
2
center 0
cuts
0
0
0
1
2
2
the whole prefix is a palindrome:
cuts[1]
=
0
s =
"aab"
n =
3
s
a
0
a
1
b
2
center 1
cuts
0
0
0
1
2
2
center = 1
grow odd and even palindromes around 'a'
s =
"aab"
n =
3
s
a
0
a
1
b
2
center 1
+1
cuts
0
0
0
1
2
2
cuts[
0
] + 1 =
1
is not better, keep
cuts[1] = 0
s =
"aab"
n =
3
s
a
0
a
1
b
2
center 2
cuts
0
0
0
1
2
2
center = 2
grow odd and even palindromes around 'b'
s =
"aab"
n =
3
s
a
0
a
1
b
2
center 2
+1
cuts
0
0
0
1
1
2
cut before 2:
cuts[2]
= cuts[
1
] + 1 =
0
+ 1 =
1
s =
"aab"
n =
3
cut
s
a
0
a
1
b
2
cuts
0
0
0
1
1
2
aa
|
b
, 1 cut
algo
master
.
io
Step:
Fewest cuts so every piece of "aab" is a palindrome?
0 / 13
Input
Simple
Palindrome heavy
Full palindrome
Mixed
Custom
s
=
aab
0 / 13
algo
master
.
io
Step:
Fewest cuts so every piece of "aab" is a palindrome?
