PROBLEM LINK:
Author: Varun Singh
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
DP
PROBLEM:
Given a string s, find all distinct strings of length 2 or 3, which can be suffixes of this word according to the rules given.
EXPLANATION:
The problem is solved with dynamic programming. We can select an arbitrary root of any length (at least 5). Let’s reverse the string. A boolean value dp_{2,3}[n] denotes if we could split a prefix of length n to strings of length 2 and 3 so that the last string has a corresponding length. Transitions: dp_2[n] = dp_3[n-2] ∨ (dp_2[n-2] ∧ s[n-3;n-2] ≠ s[n-1;n]). Similarly, dp_3[n] = dp_2[n-3] ∨ (dp_3[n-3] ∧ s[n-5;n-3] ≠ s[n-2;n]). If any of dp_k[n] is true we add the corresponding string to the set of answers.
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.