# Problem Link:

# Difficulty:

Easy

# Pre-requisites:

Dynamic Programming

# Problem:

A W-String is defined as a string consisting of lower-case alphabets, and exactly 3 "#"s that divide the string into 4 non-empty contiguous parts, where each part consists of the same alphabet. Given a string S, find the length of the longest W-String 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, P1-1], [P1+1, P2-1], [P2+1, P3-1], [P3+1, N-1]. We further should disregard cases when any one of the above yields an “empty” string.

Let cnt*[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, P1-1]

- 1 (# character)

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

- 1 (# character)

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

- 1 (# character)

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

for all potential W-Strings (that is, they have all “greedy choice of character” values > 0).

Precomputing values of cnt*[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