C#으로 주어진 문자열이 헤테로그램(Heterogram)인지 확인하는 방법

헤테로그램(Heterogram)은 문자열에 중복된 알파벳이 하나도 없는 문자열을 의미합니다. 즉, 모든 문자가 한 번씩만 등장해야 합니다.

예를 들어 다음 단어들은 모두 헤테로그램입니다.

Mobile
Cry
Laptop

헤테로그램 판별 원리

판별 방법은 간단합니다. 크기 26의 정수 배열을 만들어 각 알파벳의 등장 여부를 기록하고, 문자열의 처음부터 끝까지 한 글자씩 순회하며 이미 등장한 적 있는 문자를 만나면 즉시 false를 반환하면 됩니다.

for (int i = 0; i < len; i++) {
    if (val[str[i] - 'a'] == 0)
        val[str[i] - 'a'] = 1;
    else
        return false;
}

위 코드에서 len은 입력 문자열의 길이이고, str[i] - 'a' 연산을 통해 각 소문자 알파벳을 0부터 25 사이의 배열 인덱스로 변환합니다. 해당 인덱스 값이 0이면 아직 등장하지 않은 문자이므로 1로 표시하고, 이미 1이라면 중복 문자가 존재한다는 뜻이므로 바로 false를 반환합니다.

전체 예제 코드

using System;

public class GFG {
    static bool checkHeterogram(string str, int len) {
        int[] val = new int[26];

        for (int i = 0; i < len; i++) {
            if (val[str[i] - 'a'] == 0)
                val[str[i] - 'a'] = 1;
            else
                return false;
        }
        return true;
    }

    public static void Main() {
        string str = "mobile";

        // 입력된 문자열의 길이
        int len = str.Length;

        if (checkHeterogram(str, len))
            Console.WriteLine("String is Heterogram!");
        else
            Console.WriteLine("String is not a Heterogram!");
    }
}

실행 결과

String is Heterogram!

참고 사항

위 구현은 소문자 알파벳만 처리하도록 작성되었습니다. 대소문자가 섞인 문자열을 검사하려면 str.ToLower()로 먼저 변환하거나, 공백·특수문자를 제외하는 전처리 과정을 추가하는 것이 좋습니다. 이 알고리즘은 문자열 길이에 비례하여 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가로 사용하는 배열의 크기가 고정되어 있어 공간 복잡도는 O(1)입니다.