Java에서 문자열에서 고유 문자의 가장 긴 부분 문자열을 찾는 방법

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

가장 긴 모든 창을 반환해야하는 경우 최대 길이와 일치하는 창 목록을 유지해야합니다.

Google 인터뷰 질문

참고 문헌 :

Java HashMap

최근 댓글