Leetcode-2024:Maximize the Confusion of an Exam

PPLongAbout 8 min

Leetcode-2024:Maximize the Confusion of an Exam

Reference

📖 2024. Maximize the Confusion of an Exam

A teacher is writing a test with n true/false questions, with 'T' denoting true and 'F' denoting false. He wants to confuse the students by maximizing the number of consecutive questions with the same answer (multiple trues or multiple falses in a row).

You are given a string answerKey, where answerKey[i] is the original answer to the ith question. In addition, you are given an integer k, the maximum number of times you may perform the following operation:

Change the answer key for any question to 'T' or 'F' (i.e., set answerKey[i] to 'T' or 'F').

Return the maximum number of consecutive 'T's or 'F's in the answer key after performing the operation at most k times.

Example 1:

Input: answerKey = "TTFF", k = 2
Output: 4
Explanation: We can replace both the 'F's with 'T's to make answerKey = "TTTT".
There are four consecutive 'T's.

Example 2:

Input: answerKey = "TFFT", k = 1
Output: 3
Explanation: We can replace the first 'T' with an 'F' to make answerKey = "FFFT".
Alternatively, we can replace the second 'T' with an 'F' to make answerKey = "TFFF".
In both cases, there are three consecutive 'F's.

Example 3:

Input: answerKey = "TTFTTFTT", k = 1
Output: 5
Explanation: We can replace the first 'F' to make answerKey = "TTTTTFTT"
Alternatively, we can replace the second 'F' to make answerKey = "TTFTTTTT". 
In both cases, there are five consecutive 'T's.

Constraints:

n == answerKey.length
1 <= n <= 5 * 104
answerKey[i] is either 'T' or 'F'
1 <= k <= n

2024.9.2

Thinking 🤔

Max possible count & Continuity
Limited in no more than K ( $S t e p s \leq K$ )actions.
Possible Convert: True/False -> 1/0
DP ?

Solution

DP (Overtime)

Why dp?

Be aware of the continuity of the result.

Take F[i]: Max continuous count of certain char in substring(0, i + 1)

F [i] = {\begin{cases} F [i - 1] (C e r t a i n C o n d i t i o n) \\ F [i - 1] + 1 (C e r t a i n C o n d i t i o n) \end{cases}

But don’t figure out Certain Condition here...

Problem Model Conversion

Core 🌟 : Calculate the maximum number of consecutive* 'T's or 'F's in the answer key after performing the operation at most k times in each substring

DP Formula Inference

dp[s][e]: min(t, f) in substring[s, e]

d p [i] [j] = m i n (c o u n t (t), c o u n t (f))

r e s u l t = m a x (e - i + 1) (d p [i] [e] \leq k)

Take TTFFFT & K = 1 as an example

	end	0	1	2	3	4	5
start	0	0	0	1	2	2	3
	1	/	0	1	1	1	2
	2	/	/	0	0	0	1
	3	/	/	/	0	0	1
	4	/	/	/	/	0	1
	5	/	/	/	/	/	0

class Solution {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        int n = answerKey.length();
        int[][] dp = new int[n][n];
        int res = 0;

        for (int s = 0; s < n; s++) {
            for (int e = s; e < n; e++) {
                if (s == e) {
                    dp[s][e] = 0;
                    continue;
                }
                // Calculate numbers of min(t, s)
                int t = 0;
                for (int i = s; i <= e; i++) {
                    if (answerKey.charAt(i) == 'T') {
                        t++;
                    } 
                }
                dp[s][e] = Math.min(t, e - s + 1 - t);
                if (dp[s][e] <= k && e - s + 1 > res) {
                    res = e - s + 1;
                }
            }
        }
        return res;
    }
}

Complexity Analysis
Time Complexity: $O (N^{3})$
Zone Complexity: $O (N^{2})$

Optimzation 1 - Reduce Extra Iterate

Calculate dp[s][e] by previous result.

We know current added char
We know t & f count in previous substring(dp[s][e - 1]).

class Solution {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        int n = answerKey.length();
        int[][] dp = new int[n][n];
        char[][] charArr = new char[n][n];
        int res = 1;

        for (int s = 0; s < n; s++) {
            for (int e = s; e < n; e++) {
                if (s == e) {
                    dp[s][e] = 0;
                    charArr[s][e] = answerKey.charAt(e) == 'T' ? 'F' : 'T';
                    continue;
                }
                
                if (answerKey.charAt(e) != charArr[s][e - 1]) {
                    dp[s][e] = dp[s][e - 1];
                    charArr[s][e] = charArr[s][e - 1];
                } else if (e - s - dp[s][e - 1] >= dp[s][e - 1] + 1){
                    dp[s][e] = dp[s][e - 1] + 1;
                    charArr[s][e] = charArr[s][e - 1];
                } else {
                    dp[s][e] = e - s - dp[s][e - 1];
                    charArr[s][e] = charArr[s][e - 1] == 'T' ? 'F' : 'T';
                }
                if (dp[s][e] <= k && e - s + 1 > res) {
                    res = e - s + 1;
                }
            }
        }
        return res;
    }
}

Complexity Analysis
Time Complexity: $O (N^{2})$
Zone Complexity: $O (N^{2})$

Optimzation 2 - Optimze Extra Zone

`Cause DP perspective, we can use optimzation of Rolling Array to reduce dimension of Zone Complexity.

Because we never use dp[s - 1][xxx].

class Solution {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        int n = answerKey.length();
        int[] dp = new int[n];
        char[] charArr = new char[n];
        int res = 1;

        for (int s = 0; s < n; s++) {
            for (int e = s; e < n; e++) {
                if (s == e) {
                    dp[e] = 0;
                    charArr[e] = answerKey.charAt(e) == 'T' ? 'F' : 'T';
                    continue;
                }
                if (answerKey.charAt(e) != charArr[e - 1]) {
                    dp[e] = dp[e - 1];
                    charArr[e] = charArr[e - 1];
                } else if (e - s - dp[e - 1] >= dp[e - 1] + 1){
                    dp[e] = dp[e - 1] + 1;
                    charArr[e] = charArr[e - 1];
                } else {
                    dp[e] = e - s - dp[e - 1];
                    charArr[e] = charArr[e - 1] == 'T' ? 'F' : 'T';
                }
                if (dp[e] <= k && e - s + 1 > res) {
                    res = e - s + 1;
                }
            }
        }
        return res;
    }
}

Complexity Analysis
Time Complexity: $O (N^{2})$
Zone Complexity: $O (N)$

But cause the time complexity is at lease $O (N^{2})$ , not satisfied this question. We should find another way.

Sliding Window

Sliding Window (Copy)

To think this through, we should think through things below:

Convert Question Model :eyes:

See through this question scene and convert it to a more universal or abstract question model.

Origin: Calculate the maximum number of consecutive 'T's or 'F's in the answer key after performing the operation at most k times in each substring

Conversion: Get the substring as long as possible which contains the minimum number of consecutive 'T's or 'F'(Min(F, T) == K)

So due to the features interval and mobility, we can use thought of Sliding Window.

class Solution {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        return Math.max(maxConsecutiveChar(answerKey, k, 'T'), maxConsecutiveChar(answerKey, k, 'F'));
    }

    public int maxConsecutiveChar(String answerKey, int k, char ch) {
        int n = answerKey.length();
        int ans = 0;
        for (int left = 0, right = 0, sum = 0; right < n; right++) {
            sum += answerKey.charAt(right) != ch ? 1 : 0;
            while (sum > k) {
                sum -= answerKey.charAt(left++) != ch ? 1 : 0;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

// 作者：力扣官方题解
// 链接：https://leetcode.cn/problems/maximize-the-confusion-of-an-exam/solutions/1368825/kao-shi-de-zui-da-kun-rao-du-by-leetcode-qub5/

Complexity Analysis
Time Complexity: $O (N)$
Zone Complexity: $O (1)$

Double Pointer 👍

Same with the Sliding Window thought.

class Solution {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        int n = answerKey.length();
        int t = 0;
        int f = 0;
        int res = 1;
        int s = 0;
        int e = 0;
        for (; e < n; e++) {
            // Move Start Index
            while (Math.min(t, f) == k + 1) {
                if (answerKey.charAt(s++) == 'T') {
                    t--;
                } else {
                    f--;
                }
            }
            
            // Move End Index
            while(e < n) {
                if (answerKey.charAt(e) == 'T') {
                    t++;
                } else {
                    f++;
                }
                if (Math.min(t, f) > k) {
                    break;
                }
                e++;
            }
            res = Math.max(res, e - s);

        }
        return res;
    }
}

Complexity Analysis
Time Complexity: $O (N)$
Zone Complexity: $O (1)$

Reflection 🤔

Reflection

Learn to abstract a specific question or convert a question to a more universal/common/understand math model. And then use different solution thought logic.
Connecting array with DP is good, but remember connect Array & interval calculation/feature with Slide Window
Think bigger, think more abstract. Don’t just think a specific question like how to turn t to f and memorize usage of action counts. Before think the details, think the core part of the problem first.

2022.3.30

Thinking

Goal: Change characters to the maximum number of consecutive identical characters within a given number of operations
Idea: To achieve the maximum number of consecutive identical characters, the characters changed in k operations should all be the same
Possible approach:
Idea
- Direct: Find the maximum identical subsequence, and the number of intervals between the subsequence and another identical character sequence
- Advanced:
  - Bitwise operations
  - Can string->array->one traversal solve the problem

Solution

Sliding Window

I didn't expect the idea of sliding window. I only thought of it after seeing the hint of the solution. It was also very troublesome to do.

Instead of changing it myself, it is better for it to change. I maintain a range with the maximum number of characters that can be operated. If it exceeds the range, I will move to the next character in the first operation range, which is equivalent to changing the starting point of the range.

 public int maxConsecutiveAnswers(String answerKey, int k) {
   	return Math.max(findMaxSequence(answerKey,k,1),findMaxSequence(answerKey,k,0));
 }
 int findMaxSequence(String s, int k, int mode) {
    char a = (mode==1)?'F':'T';
    char b = (mode==1)?'T':'F';
    int count = 0;
    int gap  = 0;
    int max = 0;
    int start = 0;
    for(int i = 0 ; i < s.length(); i++) {
        if(s.charAt(i) == a){
            if(gap < k){
                gap++;
                if(i == s.length() - 1) {
                    count = i - start + 1;
                    max = Math.max(count,max);
                }
            }else{
                count = i - start ;
                max = Math.max(count,max);
                // 左移开始字符到第一个操作改变字符的下一个
                while(start < s.length() - 1 && s.charAt(start++) == b);
                if(i == s.length() - 1) {
                    count = i - start + 1;
                    max = Math.max(count,max);
                }
            }
        }else{
            if(i == s.length() - 1) {
                count = i - start + 1;
                max = Math.max(count,max);
            }
        }

    }
    return max;
}

Disadvantage: Over-consider the case of i = s.length() - 1

Optimization: Queue Cache

Original intention: When the number of operations is greater than the limit value k, it is necessary to traverse from the first interval to find the first operation character, which wastes time. You can use a queue to cache the indexes of the operated characters, and then directly poll them.

  	public int maxConsecutiveAnswers(String answerKey, int k) {
        return Math.max(findMaxSequence(answerKey,k,1),findMaxSequence(answerKey,k,0));
    }
    int findMaxSequence(String s, int k, int mode) {
        int max = 0;
        // b represent substitute
        char b = (mode == 0?'F':'T');

        Queue<Integer> list_s = new LinkedList<>();
        list_s.offer(0);
        for(int i = 0 ; i < s.length(); i++) {
            if(s.charAt(i) == b){
                if(list_s.size() <= k){
                    list_s.offer(i +1);
                }else{
                    list_s.offer(i +1);
                    int a = list_s.size() == 0? 0 :list_s.poll();
                    max = Math.max(i - a ,max);
                    if(i == s.length() - 1)
                        break;
                }
            }
            if(i == s.length() - 1) {
                int a = list_s.size() == 0? 0 :list_s.peek();
                max = Math.max(i - a + 1,max);
            }
        }
        return max;
    }

I don't understand why the time is still a little slower, maybe it's because of the creation of the queue?

Simplicity

LeetCode problem solution, similar to my first problem solution

 public int maxConsecutiveChar(String answerKey, int k, char ch) {
    int n = answerKey.length();
    int ans = 0;
    // 注意这种赋值，不错
    for (int left = 0, right = 0, sum = 0; right < n; right++) {
        // sum记录操作数
        sum += answerKey.charAt(right) != ch ? 1 : 0;
        // 移动起点到第一次操作的下一个位置
        while (sum > k) {
            sum -= answerKey.charAt(left++) != ch ? 1 : 0;
        }
        // 消除代码冗余
        // 每次循环都比较一次，就不用做i=s.length() - 1的判断了
        ans = Math.max(ans, right - left + 1);
    }
    return ans;
}

Double Pointer (Copy)

This idea is OK. The essence is: there is no specific requirement on whether T or F changes. I calculate the values of t operation and f operation at the same starting and ending points.

If there is no overflow, normal growth
If only one of the operands overflows, it means that the other operand has not overflowed, indicating that the total length of the other operand is greater than the total length of this operand, and the operation can continue.
If both overflow, it means that neither of them works. Calculate the maximum value and move l to the situation where neither overflows
- ~~❓ But this raises a question. Why is the condition for L to move to the position where both do not overflow, rather than one of them does not overflow? For example...FFFFFTTFT, it has to move to the position of T and start again, but can it be guaranteed that there is no maximum value when the starting point starts from the previous few Fs? ~~
- I didn't read the question. The condition is that when both are greater than k, move forward to left, but as long as one is not satisfied, it can be calculated, which is correct. When T meets the situation, F may increase to much greater than K, but it doesn't matter because the interval is maintained. When none of them meet the conditions later, all Fs encountered will be f-- backed down.

class Solution {
	public int maxConsecutiveAnswers(String answerKey, int k) {
        // l:起始位置 r: 结束位置
		int l = 0, r = 0;
		int len = answerKey.length();
		char[] cs = answerKey.toCharArray();
        // t:改变T的操作次数 f:改变F的操作次数
		int t = 0, f = 0;
		int ans = 0;
		while (r < len) {
			char R = cs[r];
			if (R == 'T') {
				t++;
			} else {
				f++;
			}
            // 重点
			if (t > k && f > k) {
				ans = Math.max(ans, r - l);
				while (t > k && f > k) {
					char L = cs[l];
					if (L == 'T') {
						t--;
					} else {
						f--;
					}
					l++;
				}
			}
			r++;
		}
        // 计算下最后的值
		ans = Math.max(ans, len - l);
		return ans;
	}
}

// 作者：wa-pian-d
// 链接：https://leetcode-cn.com/problems/maximize-the-confusion-of-an-exam/solution/2024-kao-shi-de-zui-da-kun-rao-du-java-b-86wg/

Reflection

I am not familiar with sliding windows. I did not think of sliding windows when I was doing it. I have not done sliding window questions for a long time. Characteristics of sliding window questions: There are limited values, and the values in the calculation range (continuous), preferably in an array. Consolidate
Too many judgments on special cases, causing confusion in thinking and redundant code
Think clearly before writing code…………