When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Vesper_Lynd's blog

By Vesper_Lynd, history, 5 years ago, In English

IN THIS PROBLEM I DON'T UNDERSTAND THE GRAPH APPROACH FOR THIS PROBLEM? CAN ANYBODY HELP OUT!! PROBLEM LINK TUTORIAL LINK

  • Vote: I like it
  • -23
  • Vote: I do not like it

»
5 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Make a graph with vertexes 1, 2, ..., n; for each i a substring sisi + 1...si + k - 1 should be a palindrome, so for each i you should make edges between si and si + k - 1, between si + 1 and si + k - 2, etc. For each connected component in this graph, letters should be equal in each vertex of that component; if number of components is e then the answer is me