Problem Link:
Difficulty:
Easy
Prerequisites:
Dynamic Programming
Problem:
A WString is defined as a string consisting of lowercase alphabets, and exactly 3 "#"s that divide the string into 4 nonempty contiguous parts, where each part consists of the same alphabet. Given a string S, find the length of the longest WString that is a subsequence of S, with the added constraint that the three chosen #positions in W, are consecutive #positions in S.
Explanation:
Let us suppose that we choose our three #positions as P1, P2 and P3. After fixing P1, P2, P3, we greedily choose the most frequent character from [0, P11], [P1+1, P21], [P2+1, P31], [P3+1, N1]. We further should disregard cases when any one of the above yields an “empty” string.
Let cnt[i][k] = Number of times character k occurs in S[0…i]. Then, given P1, P2, P3, we just need to calculate
max(cnt[P1][k] : 1<=k<=26) (greedy choice of character in [0, P11]

1 (# character)

max(cnt[P2][k]  cnt[P1][k] : 1<=k<=26) (greedy choice of character in [P1+1, P21]

1 (# character)

max(cnt[P3][k]  cnt[P2][k] : 1<=k<=26) (greedy choice of character in [P2+1, P31]

1 (# character)

max(cnt[N1][k]  cnt[P1][k] : 1<=k<=26) (greedy choice of character in [P3+1, N1],
for all potential WStrings (that is, they have all “greedy choice of character” values > 0).
Precomputing values of cnt[i][k] will take time O(N * 26). Further, we can iterate over all consecutive P1,P2,P3 in O(N) time, and each will lead to a calculation of 26 time. Thus overall complexity will be O(N * 26 * T). This can be sped up by a constant factor by precomputing MaxLeft(i) and MaxRight(i) which will find the maximum frequency of a single letter to the left or to the right of position i respectively.
Setter’s Solution:
Can be found here
Tester’s Solution:
Can be found here