[LeetCode] 2272. Substring With Largest Variance

2272. Substring With Largest Variance

Hard

The variance of a string is defined as the largest difference between the number of occurrences of any 2 characters present in the string. Note the two characters may or may not be the same.

Given a string s consisting of lowercase English letters only, return the largest variance possible among all substrings of s.

A substring is a contiguous sequence of characters within a string.

 

Example 1:

Input: s = "aababbb"
Output: 3
Explanation:
All possible variances along with their respective substrings are listed below:
- Variance 0 for substrings "a", "aa", "ab", "abab", "aababb", "ba", "b", "bb", and "bbb".
- Variance 1 for substrings "aab", "aba", "abb", "aabab", "ababb", "aababbb", and "bab".
- Variance 2 for substrings "aaba", "ababbb", "abbb", and "babb".
- Variance 3 for substring "babbb".
Since the largest possible variance is 3, we return it.

Example 2:

Input: s = "abcde"
Output: 0
Explanation:
No letter occurs more than once in s, so the variance of every substring is 0.

 

Constraints:

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

---

문제 풀이

Kadane 알고리즘

• 주어진 문장에서 두 개의 알파벳을 선택하여 알파벳의 개수 차이의 최대값을 구해야한다.
• 알파벳 두개가 포함되는 배열은 부분 연속 배열로 답으로 선택될 수 있는 배열의 범위는 연속적으로 연결되어 있어야한다.
• 문제 제한은 10^4라 브루트 포스로도 풀릴 것 같지만 for문을 사용하면 3중포문을 사용해야해서 시간 제한에 걸린다.
• 부분합의 최대 값을 구하는 문제에서 사용하는 알고리즘은 Kadane 알고리즘 '카데인'이다. 
• 이 알고리즘을 사용하여 푸는 문제중 easy 문제는 아래 첨부하였다.

https://leetcode.com/problems/maximum-subarray 

Maximum Subarray - LeetCode

• 최대 값을 가진 부분 배열 합을 구할때 음수 값이 있기 때문에 조금 복잡하다.
• 하지만 이 알고리즘을 사용하면 선형 시간내에 풀 수 있다. 
• 우선 최대값을 저장할 변수를 두개 만든다. 
• 하나는 부분합의 값이 계속 바뀌기 때문에 그에 대한 최대 값이며, 나머지 하나는 리턴할 최대 값이다.
• -1, 2, -6, 3, 7 배열이 있다고 가정했을때 최대 합 값은 10이다. 
• 배열의 첫자리부터 더해 나가며 값을 비교하는데, 현재 값과 이전까지 더했던 값과의 합과 비교한다. 
• 2 값에 도착했을때, 이전 값과의 합은 1이고 현재 값은 2이다. 
• 최대값을 2로 바꿔주고, 이 값을 반환할 값과 비교하여 최대값으로 만들어준다. 
• 이렇게 하는 이유는 -1은 도움이 되지 않기 때문이다. 
• 3에 도착했을때도 마찬가지고 수행되고, 마지막에 3, 7을 더했을때 최대값이 된다. 

Kadane 알고리즘 응용

• 주어진 문장의 알파벳 개수를 Counter로 구해준다. 
• 그리고 Permutations을 이용하여 두개의 알파벳을 구성한다. 
• a는 시작 알파벳이고 b는 최대 합 값 계산시에 개수를 빼줄 알파벳이다. 
• 두 글자를 순열(선택)로 만들어 문장에서 부분 수열 최대 합을 구한다.
• 글자가 a, b 둘 중 하나도 포함되지 않는다면 무시하고, a일때는 a의 개수를 b일때는 b의 개수를 올린다.
• b의 남은 개수를 줄여나가는 이유는 조금 전의 카데인 알고리즘을 응용한 부분이다.
• 만일 b의 개수가 a의 개수보다 많고 b의 전체 개수가 1개 이상이면 이 말은 시작지점부터 끝까지 탐색을 해도 현재 부분 배열에서는 a의 개수가 b의 개수보다 월등히 높아질 수 없기 때문에 a, b의 개수 값을 초기화하여 다음 알파벳부터 다시 부분 배열이 시작된다. 
• 그리고 최대 값을 취할때 b의 개수를 확인하는 이유는 문제에서 두 알파벳이 꼭 함께 있어야 Variance를 계산할 수 있기 때문이다. 

소스 코드

class Solution:
    def largestVariance(self, s: str) -> int:
        counter = Counter(s)
        res = 0
        for a, b in permutations(counter, 2):
            count_a, count_b = 0, 0
            remain_b = counter[b]
            for c in s:
                if c != a and c != b:
                    continue
                if c == a:
                    count_a += 1
                elif c == b:
                    count_b += 1
                    remain_b -= 1
                if count_a < count_b and remain_b > 0:
                    count_a, count_b = 0, 0
                if count_b > 0:
                    res = max(res, count_a - count_b)
        return res