Minimal Character Reassignment

Easy

0/40

0 upvote

Problem statement

You are given a string s consisting of lowercase English letters. Your task is to find the minimum number of character replacements required so that no two adjacent characters in the string are the same.

You can replace any character at any position with any other lowercase English letter.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first and only line of input contains a single string s.

Output Format:

The output should be a single integer representing the minimum number of replacements needed.

Note:

The goal is to eliminate all occurrences where s[i] == s[i-1].
When a character s[i] is the same as its preceding character s[i-1], a replacement is necessary. We only need to count how many times this occurs.
The problem asks for the count of replacements, not the modified string itself.

Sample Input 1:

aab

Sample Output 1:

Explanation for Sample 1:

The string is "aab".
  We compare s[1] ('a') with s[0] ('a'). They are the same. We must perform one replacement.
  We compare s[2] ('b') with s[1] ('a'). They are different. No replacement is needed here.
  Total minimum replacements = 1.

Expected Time Complexity:

The expected time complexity is O(N), where N is the length of the string s.

Constraints:

1 <= s.length <= 10^5
s consists of lowercase English letters.

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Minimal Character Reassignment

Console