Interview question #4

Revision en6, by bablu_45, 2019-07-19 19:02:34

Normal palindrome is defined as a string that reads the same backwards as forwards, for example "abccba". Chunked palindrome is defined as a string that you can split into chunks and it will form a palindrome. For example, "volvo". You can split it into (vo)(l)(vo). Let A = "vo", B = "l", so the original string is ABA which is a palindrome.

Given a string str, find the maximum number of chunks we can split that string to get a chuncked palindrome.

For eg

:- "aaaaaa", output is 6 ((a)(a)(a)(a)(a)(a))

:- "volvol" output is 2 ((vol)(vol))

Length of string <=2*(10^3)

I can think of a greedy way to solve this problem but not able to prove if it's optimal.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English bablu_45 2019-07-19 22:22:50 2 Tiny change: 'g <=2*(10^3)\n\nI can' -> 'g <=2*(10^4)\n\nI can'
en6 English bablu_45 2019-07-19 19:02:34 2 Tiny change: 'g <=2*(10^4)\n\nI can' -> 'g <=2*(10^3)\n\nI can'
en5 English bablu_45 2019-07-19 16:31:02 4 Tiny change: ' string <=10^4\n\nI can ' -> ' string <=2*(10^4)\n\nI can '
en4 English bablu_45 2019-07-19 16:30:32 27 Tiny change: '(vol))\n\nI can ' -> '(vol))\n\nLength of string <=10^4\n\nI can '
en3 English bablu_45 2019-07-19 08:53:23 3
en2 English bablu_45 2019-07-19 08:52:04 10
en1 English bablu_45 2019-07-19 08:51:26 667 Initial revision (published)