C++에서 문자 X를 최소 한 번 포함하는 부분 문자열 개수 구하기

문제 정의

문자열 str과 문자 X가 주어졌을 때, X를 최소 한 번 이상 포함하는 부분 문자열(substring)의 개수를 구하는 것이 이 글의 목표입니다.

예를 들어 str이 “abc”이고 X가 ‘a’라면, 조건을 만족하는 부분 문자열은 “a”, “ab”, “abc”로 총 3개입니다.

예제 1

입력: str = “aabccd”, X = ‘c’

출력: 14

설명: ‘c’를 하나 이상 포함하는 부분 문자열은 “c”, “c”, “bc”, “cc”, “cd”, “abc”, “bcc”, “ccd”, “aabc”, “abcc”, “bccd”, “aabcc”, “abccd”, “aabccd”로 총 14개입니다.

예제 2

입력: str = “settings”, X = ‘s’

출력: 15

설명: 첫 번째 ‘s’에서 시작하는 부분 문자열은 “s”, “se”, “set”, “sett”, “setti”, “settin”, “setting”, “settings”의 8개이고, 마지막 ‘s’에서 끝나는 부분 문자열은 “ettings”, “ttings”, “tings”, “ings”, “ngs”, “gs”, “s”의 7개입니다. 두 집합을 합하면 총 15개입니다.

접근 방법

길이가 n인 문자열이 가질 수 있는 전체 부분 문자열의 개수는 n × (n+1) / 2입니다. 이 중에서 조건을 만족하는 것만 정확하게 세기 위해, 여기서는 “각 X를 마지막으로 포함하는 부분 문자열”을 기준으로 개수를 세는 방식을 사용합니다.

핵심 아이디어는 다음과 같습니다. 인덱스 i의 문자가 X일 때, 이 X를 반드시 포함하는 부분 문자열의 수는 시작 지점 후보 수와 끝 지점 후보 수의 곱으로 계산됩니다.

직전 X 이후(또는 문자열 시작)부터 현재 위치 i까지의 거리를 temp라 할 때, 가능한 시작 지점은 temp + 1개입니다.
현재 위치 i를 끝으로 삼거나 뒤쪽으로 확장하는 경우의 수는 length − i개입니다.
따라서 str[i] == X인 순간마다 (temp + 1) × (length − i)를 결과에 더하고, temp를 0으로 초기화한 뒤 다음 X를 찾아 계속 진행합니다.

이 방식을 사용하면 모든 부분 문자열이 정확히 한 번씩만 계산되므로 중복 없이 답을 구할 수 있습니다.

알고리즘 단계

문자열 str, 길이 length, 문자 x를 입력받습니다.
count = 0, temp = 0으로 초기화합니다. temp는 직전 X 이후에 등장한 연속된 문자 수를 의미합니다.
i = 0부터 length − 1까지 문자열을 순회합니다.
str[i]가 x가 아니면 temp를 1 증가시킵니다.
str[i]가 x이면 (temp + 1) × (length − i)를 count에 더하고 temp를 0으로 초기화합니다.
순회가 끝나면 count를 반환합니다. 이 값이 곧 X를 최소 한 번 포함하는 부분 문자열의 개수입니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

int sub_x(string str, int length, char x){
    int count = 0;
    int temp = 0;
    for (int i = 0; i < length; i++){
        if (str[i] == x){
            int temp_2 = temp + 1;
            count = count + temp_2 * (length - i);
            temp = 0;
        }
        else{
            temp++;
        }
    }
    return count;
}

int main(){
    string str = "abcabbc";
    int length = str.length();
    char x = 'a';
    cout<<"Count of sub-strings that contain character X at least once are: "<<sub_x(str, length, x);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Count of sub-strings that contain character X at least once are: 19

문자열 “abcabbc”에서 ‘a’는 인덱스 0과 3에 위치합니다. 인덱스 0의 ‘a’는 1 × 7 = 7개, 인덱스 3의 ‘a’는 3 × 4 = 12개의 부분 문자열에 기여하므로 전체 개수는 7 + 12 = 19개입니다.

복잡도 분석

시간 복잡도: O(n) — 문자열을 한 번만 순회하면 됩니다.
공간 복잡도: O(1) — 추가 배열 없이 상수 개의 변수만 사용합니다.