2063. Vowels of All Substrings

2063. Vowels of All Substrings

https://leetcode.com/problems/vowels-of-all-substrings/

문제

풀이(처음 풀었던 답)

1. "a"일 때 => 1
2. "ab"일 때 => "b"는 "aeiou"가 아니므로 그 전의 값 1
3. "aba"일 때 => "a"는 "aeiou"이므로 그 전의 값 + 1 = 2
4. "abae"일 때 => "e"는 "aeiou"이므로 그 전의 값 + 1 =3 ....
이런식으로 하여 n^2이라는 시간복잡도를 가진다.

풀이(결과)

테스트케이스 조건에서 문자열이 10^5라 하였으므로 시간복잡도 n^2는 상당히 좋지 않은 알고리즘이다.

풀이(두번째 풀이)

규칙이 존재한다.
i = 0일 때 "a"이므로 1
i = 1일 때 "b"가 2개 있고 이전의 값 1이므로 1+0 = 1
i = 2일 때 "a"가 3개 있고 이전의 값 1 이므로 4
i = 3일 때 "e"가 4개 있고 이전의 값 4이므로 8이다.
이것을 코드화 하면

풀이(결과)