[2024] day 122. Leetcode 1915. Number of Wonderful Substrings

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 4월 30일 (화)
Leetcode daily problem

1915. Number of Wonderful Substrings

https://leetcode.com/problems/number-of-wonderful-substrings/?envType=daily-question&envId=2024-04-30

Problem

주어진 문자열에서 'Wonderful'한 부분 문자열 개수를 세는 문제이다. 'Wonderful 한 부분문자열' 이란 문자열에서 같은 문자가 최대 한 번 등장하는 부분문자열을 의미한다.

예를 들어 "ccjjc"와 "abab"는 Wonderful한 부분 문자열이지만, "ab"는 해당하지 않는다.

10개의 소문자 영어 문자('a' ~ 'j')로 구성된 문자열 단어가 주어질 때 단어에서 'Wonderful'한 부분 문자열의 수를 반환한다.
동일한 하위 문자열이 단어에 여러 번 나타나는 경우 각 발생을 개별적으로 계산한다.

하위 문자열은 문자열에서 연속된 문자 시퀀스이다.

Solution

해당 문제를 해결하기 위해서는 sliding window 방식을 사용해서 각 부분 문자열이 Wonderful 한지 확인한다.
각 윈도우에서 문자의 등장 횟수를 유지하고, 해당 윈도우가 wonderful 한 부분 문자열인지 확인하고 그 개수를 센다.

Code

Complexicity

시간 복잡도

공간 복잡도