Minimum Days
Problem Overview
The string is finished when no two neighboring letters are equal.
Intuition
The string is finished when no two neighboring letters are equal. A question mark may sit beside anything, because the rule only constrains a letter that is still present. The number of equal neighboring pairs is therefore the only quantity that matters. That count is taken once at the start. Each day replaces one index from the permutation with a question mark. That replacement can break the pair on its left and the pair on its right, and it cannot create a new forbidden pair, because a question mark never forces a mismatch. When the live count of equal pairs reaches zero, the string already satisfies the rule, and that day number is the answer. If the original string has no equal neighbors, the answer is 0 without using the permutation.
Algorithm
- 1Copy the string into a character array and count every index i where the character equals the next one.
- 2Return 0 when that count is already zero.
- 3For each day, read the index from the permutation.
- 4If the left neighbor equals the current character, lower the count by one. If the right neighbor equals the current character, lower the count by one.
- 5Replace the current character with a question mark. Return the day number when the count hits zero.
Example Walkthrough
Input: s = "aabb", p = [2, 1, 3, 0]
- 1. The original string has one equal pair at indices 0 and 1, so the count starts at 1.
- 2. Day 1 replaces index 2 and leaves the pair "aa" in place.
- 3. Day 2 replaces index 1, breaks that pair, and the count falls to 0, so the answer is 2.
Output: 2
Common Pitfalls
- • A question mark beside a letter is allowed. Do not count those pairs as forbidden.
- • The permutation visits each index once, so a position is never replaced twice.
- • Decrement the equal pair count before writing the question mark. The old letter is what matched its neighbors.
- • If the string is already valid, return 0. Do not wait for the first replacement.
// Approach: The string is valid when no two neighboring letters are equal.
// Count those equal pairs once. Each day replaces one index with '?', which
// can break at most the pair on its left and the pair on its right. When the
// live count reaches zero, that day is the answer.
// Complexity: O(n) time, O(1) extra space.
class Solution {
public int getMinimumDays(String s, int[] p) {
int n = s.length();
char[] chars = s.toCharArray();
int equalPairs = 0;
for (int i = 0; i < n - 1; i++) {
if (chars[i] == chars[i + 1])
equalPairs++;
}
if (equalPairs == 0)
return 0;
for (int day = 0; day < n; day++) {
int index = p[day];
if (index > 0 && chars[index - 1] == chars[index])
equalPairs--;
if (index + 1 < n && chars[index] == chars[index + 1])
equalPairs--;
chars[index] = '?';
if (equalPairs == 0)
return day + 1;
}
return n;
}
}