如何使用Java從String中查找唯一字符的最長子字符串

05/08/2019

這是來自Google採訪的一個問題：一個字符流停止，找到該流中唯一字符的最長子字符串。 流可以被同化為一系列字符。

通過在輸入字符上使用滑動窗口並使用在當前窗口中找到字符的時間數維護索引來解決此問題。 對於輸入的所有字符，結束窗口位置增加1，並將當前字符添加到索引。 在窗口是預期大小之前，我們從窗口的開始移除一個字符。 如果當前窗口比當前最大值長，我們保存它。 在過程結束時，我們返回最大窗口。

創建以下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

如果需要返回所有最長的窗口，我們需要維護一個與最大長度匹配的窗口列表。

谷歌面試問題

參考文獻：

Java HashMap

最近評論