How should I practice Maximum Substrings?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Snowflake online assessment problems in FastPrep.

Is Maximum Substrings associated with Snowflake?

FastPrep tags this as a Snowflake coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Dynamic Programming

Maximum Substrings

Learn this problem

● HardSnowflakeINTERNOA

See Snowflake hiring insights

Problem statement

The people in HackerLand, are getting ready for a parade. There should be no instance where a person is wearing a white-colored uniform. There is a given string color that contains lowercase English characters ('a' - 'z'). Some of the positions in the string are empty, meaning that the color of the uniform is white at that position and is denoted by the '.' character.

A beautiful string is defined as a string in which all characters are the same. For example "aaa", "zzzzz", "f" are beautiful while "aba", "aaad" are not beautiful. Replace each non-colored uniform with some lowercase English character such that the total number of substrings that are beautiful maximized.

Find the maximum total number of beautiful substrings after replacing every empty character.

Note: A substring of a string is a contiguous subsequence of that string.

Function

getMaxBeautifulSubstrings(color: String) → int

Complete the function getMaxBeautifulSubstrings in the editor.

getMaxBeautifulSubstrings has the following parameter(s):

string color: the color of each uniform

Returns

int: the maximum number of beautiful substrings possible

Examples

Example 1

color = ".a.bb."return = 13

The optimal filled string is "aaabbb". The beautiful substrings are {"a", "a", "aa", "b", "b", "b", "b", "bb", "bb", "bbb", "bbb",, "bbbb"}. The maximum possible number of beautiful substrings is 13.

Example 2

color = "p.r."return = 7

The optimal string is "prrr". The beautiful substrings are {"p", "r", "r", "r", "rr", "rr", "rrr"} The maximum possible number of beautiful substrings is 7.

Constraints

1 ≤ |color| ≤ 5000