(Leetcode) 424 - Longest Repeating Character Replacement
New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time
위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.
https://leetcode.com/problems/longest-repeating-character-replacement/description/
내가 작성한 풀이
class Solution {
public int characterReplacement(String s, int k) {
int[] count = new int[26];
int i = 0;
int j = 0;
int max = Integer.MIN_VALUE;
int result = Integer.MIN_VALUE;
while (i < s.length()) {
int index = s.charAt(i) - 'A';
count[index]++;
max = Math.max(max, count[index]);
if (i - j - max + 1 > k) {
count[s.charAt(j) - 'A']--;
j++;
}
result = Math.max(result, i - j + 1);
i++;
}
return result;
}
}
나에게는 꽤 어려운 문제였다.
일종의 window 를 도입하여 해결한다.
- 각 step마다
i를 1씩 증가시킨다. max: i와 j 사이의 가장 큰 연속된 char의 수.i - j - max + 1 > k: 현재 부분 문자열의 길이에서 가장 많이 등장한 문자의 수를 뺀 값이 허용된 치환 횟수k를 초과하는지 확인- 초과하였다면
j를 1 증가시킨다.
- 초과하였다면
- 각 step마다
result값을 계산하고 기존의result보다 큰 값이면 갱신한다.
TC, SC
시간 복잡도는 O(n)이고, 공간 복잡도는 O(1)이다.
다시 풀어보기 (240603)
지난번에 참고했던 풀이를 보지 않고 다시 풀어보았다. 다시 풀어봐도 어려운 문제였다.
class Solution {
public int characterReplacement(String s, int k) {
int[] counter = new int[26];
int countOfMostFrequent = -1;
int headPointer = 0;
int tailPointer = 0;
int maxLength = 0;
while (headPointer < s.length()) {
char head = s.charAt(headPointer);
char tail = s.charAt(tailPointer);
counter[head - 'A']++;
headPointer++;
countOfMostFrequent = getCountOfMostFrequent(counter[head - 'A'], countOfMostFrequent);
while (headPointer - tailPointer > countOfMostFrequent + k) {
counter[tail - 'A']--;
tailPointer++;
tail = s.charAt(tailPointer);
}
maxLength = Math.max(maxLength, headPointer - tailPointer);
System.out.printf("%d, %d, %s\n", tailPointer, headPointer, s.substring(tailPointer, headPointer));
}
return maxLength;
}
int getCountOfMostFrequent(int challenge, int countOfMostFrequent) {
return Math.max(challenge, countOfMostFrequent);
}
}
TC, SC
시간 복잡도는 O(n)이고, 공간 복잡도는 O(1)이다.
