[Leetcode] 1781. Sum of Beauty of All Substrings

문제 : https://leetcode.com/problems/sum-of-beauty-of-all-substrings/

---

문자열의 beauty는 가장 자주 사용되는 문자와 가장 자주 사용되지 않는 문자 사이의 빈도 차이이다.

문자열 s가 주어졌을 때 모든 하위 문자열의 beauty 합을 구해라.

---

s.length가 500 이므로 완탐을 돌린다.

2차원 반복문을 돌려서 s[start~end]에서 문자의 등장횟수를 갱신하며 탐색당시의 beauty 값을 구해 정답에 더해나간다.

for start = [0, |s|)
	문자의 등장횟수를 저장하는 map 갱신
    for end = [start, |s|)
    	s[end] 횟수 + 1
        등장횟수 map을 탐색하며 최대등장횟수, 최소등장횟수를 구해서 차이를 정답에 더한다.

 

시간복잡도는 N = |s|라 할 때, O(N^2)

---

소스코드

C++ : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/1781.%20Sum%20of%20Beauty%20of%20All%20Substrings.cpp

https://github.com/fpdjsns/Algorithm-python/blob/main/leetcode/medium/1781.%20Sum%20of%20Beauty%20of%20All%20Substrings.py