NOSTRING - Editorial

dynamic-programming
easy-medium
strings
substring

#1

PROBLEM LINK:

Practice
Contest

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.