Javaで文字ストリームから最初の非反復文字を検索する方法

連続的に入力される文字のストリームの中から、最初に現れた重複しない文字（非反復文字）を検索するには、Javaではリストとboolean型の配列を組み合わせるのが効果的です。以下にその実装例を示します。

サンプルコード

import java.util.ArrayList;
import java.util.List;
public class Demo{
    final static int max_chars = 256;
    static void non_repeating_char(){
        List<Character> my_list = new ArrayList<Character>();
        boolean[] repeat = new boolean[max_chars];
        String my_str = "Thisisasample";
        for (int i = 0; i < my_str.length(); i++){
            char x = my_str.charAt(i);
            if (!repeat[x]){
                if (!(my_list.contains(x))){
                    my_list.add(x);
                }
                else{
                    my_list.remove((Character)x);
                    repeat[x] = true;
                }
            }
            if (my_list.size() != 0){
                System.out.print("The first non-repeating character of the string is ");
                System.out.println(my_list.get(0));
            }
        }
    }
    public static void main(String[] args){
        non_repeating_char();
    }
}

実行結果

The first non-repeating character of the string is T
The first non-repeating character of the string is T
The first non-repeating character of the string is T
The first non-repeating character of the string is T
The first non-repeating character of the string is T
The first non-repeating character of the string is T
The first non-repeating character of the string is T
The first non-repeating character of the string is T
The first non-repeating character of the string is T
The first non-repeating character of the string is T
The first non-repeating character of the string is T
The first non-repeating character of the string is T
The first non-repeating character of the string is T

プログラムの仕組み

このプログラムでは、Demo というクラス内に non_repeating_char というメソッドを定義しています。処理の流れは以下のとおりです。

まず、出現中の文字を管理するための List<Character> を作成し、対象となる文字列（ここでは「Thisisasample」）を定義します。次に、文字列を先頭から1文字ずつ走査し、各文字がすでに繰り返し出現したかどうかを repeat というboolean型の配列に記録します。繰り返しが確認された文字には true が設定され、まだ一度しか出現していない文字は false のまま保持されます。

具体的には、ある文字が初めて登場した場合はリストに追加され、2回目以降に登場した場合はリストから削除されると同時に repeat 配列にフラグが立てられます。これにより、リストの先頭要素（インデックス0）が常に「現在時点で最初の非反復文字」を表すことになります。

最後に、main メソッドからこのメソッドを呼び出すことで処理が実行され、各ステップにおける最初の非反復文字がコンソールに出力されます。この例では、文字「T」が他のどの文字とも重複していないため、常に「T」が結果として表示されます。