Problem Brief

Maximize Beautiful Substrings

FULLTIMEOA

Given a string color, which contains lowercase letters (a-z) and dots (.) representing blank positions, you can replace each dot with any lowercase letter.

A beautiful substring is defined as a contiguous substring where all characters are the same. For example, "a", "bb", and "zzzz" are beautiful substrings, while "ab" and "aab" are not.

Your task is to:

Replace each dot in the string with a lowercase letter;

Maximize the total number of beautiful substrings in the final string.

Return the maximum possible number of beautiful substrings.

1Example 1

Input

color = ".a.bb."

Output

Explanation

An optimal replacement would be: "aabbbb" The beautiful substrings include: "a", "a", "aa", "b", "b", "b", "bb", "bb", "bb", "bbb", "bbb", "bbb", "bbbb" In total: 13 beautiful substrings. Output: 13

Draft autosaves locally

public int maximizeBeautifulSubstrings(String color) {
  // write your code here
}

Input

color

".a.bb."

Output