Javaを使用してStringから一意の文字の最も長いサブストリングを見つける方法

05/08/2019

これはグーグルでのインタビューからの質問です。 ストリームは文字の配列に同化できます。

この問題は、入力文字にスライディングウィンドウを使用し、現在のウィンドウで文字が見つかった回数のインデックスを維持することで解決されます。 入力のすべての文字について、ウィンドウの終了位置が1つ増え、現在の文字がインデックスに追加されます。 ウィンドウが予想されるサイズになるまで、ウィンドウの先頭からa文字を削除します。 現在のウィンドウが現在の最大値より長い場合は、保存します。 プロセスの最後に、最大ウィンドウを返します。

次のJavaファイルを作成します。

import java.util.HashMap;
import java.util.Map;

public class InterviewLongestSubString {

    protected void addCharIndex( Map<Character, Integer<g index, char in ){
	if( !index.containsKey( in ) ){
	    index.put(in, 1);
	    return;
	}
	
	// Increment and add
	index.put(in, index.get(in)+1);
    }

    protected void removeCharIndex( Map<Character, Integer> index, char in ){
	if( !index.containsKey( in ) ){
	    return;
	}
	
	int currentValue = index.get(in);
	if( currentValue == 1 ){
	    index.remove( in );
	    return;
	}
	
	// Decrement the value
	index.put(in, currentValue-1);
    }
    
    protected boolean isValidWindow(Map<Character, Integer> index, int size){
	if( index.keySet().size() > size )
	    return false;
	
	return true;
    }
    
    public String process(String in, int k){
	Map<Character, Integer> index = new HashMap<Character, Integer>();
		
	char[] tab = in.toCharArray();
	int currentWindowStart = 0, currentWindowEnd = 0; 
	int maxWindowStart = 0, maxWindowSize = 0; 
	
	// Loop on all the chars
	for(int i=0 ; i < tab.length ; i++){
	    char c = tab[i];
	    
	    addCharIndex(index, c);
	    
	    currentWindowEnd++;
	    
	    while( !isValidWindow(index,k) ){
		removeCharIndex(index, tab[currentWindowStart] );
		currentWindowStart++;
	    }
	    
	    int currentWindowSize = currentWindowEnd - currentWindowStart + 1;
	    if( currentWindowSize > maxWindowSize ){
		maxWindowSize = currentWindowSize;
		maxWindowStart = currentWindowStart;
	    }
	}
	
	// return the String found
	return in.substring(maxWindowStart,maxWindowStart+maxWindowSize-1 );
    }
    
    public static void main(String[] argv){
	InterviewLongestSubString o = new InterviewLongestSubString();
	
	String s = "aabacbebebe"; 
	System.out.println( "input = " + s );
	for(int i = 1; i < 5; i++){
	    System.out.println( "k = " + i );
	    System.out.println( "output = " + o.process(s, i) );
	    System.out.println( );
	}
    }    
}

出力は次のようになります。

input = aabacbebebe
k = 1
output = aa

k = 2
output = bebebe

k = 3
output = cbebebe

k = 4
output = aabacbebebe

すべての最長ウィンドウを返す必要がある場合は、最大長に一致するウィンドウのリストを管理する必要があります。

Googleインタビューの質問

参考文献：

Java HashMap

最近のコメント