Hackerrank Coding Interview 2. Palindrome Subsequences

Time to complete — 30minutes

Question Type = Medium

Asked in = Microsoft, Uber, Lyft, Bloomberg, Morgan Stanley, Apple, and Google.

Skills: arrays, enumeration, greedy algorithms, prefix sum

Insights — It should be read very carefully read and you must ask questions in between.

Question —

For a string s which consists only of characters ‘0’ and ‘1’, find the number of subsequences of length 5 which are palindromes.

As the answer can be really big, return the answer mod (10⁹ + 7).

Note

• A palindrome is a string that reads the same backward as forward.
• A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.
• Two subsequences are considered different if the indices of the string that forms the subsequences are different.

Example

s = “0100110”

Using 1-based indexing, the 5 subsequences are

• indices (1, 2, 3, 6, 7) -> 01010
• indices (1, 2, 3, 5, 7) -> 01010
• indices (1, 2, 4, 6, 7) -> 01010
• indices (1, 2, 4, 5, 7) -> 01010
• indices (1, 2, 5, 6, 7) -> 01110