class Solution {
    public String longestCommonPrefix(String[] strs) {
        
        if(strs.length == 1){
            return strs[0];
        }
        int longestElemLength = strs[0].length();
        int smallestElemLength = strs[0].length();
        if(smallestElemLength == 0){
            return "";
        }
        int smallestElemIndex = 0;
        
        for(int i=1; i<strs.length ;i++){
            if(strs[i].length() == 0){
                    return "";
            }else if(strs[i].length() < smallestElemLength){
                smallestElemLength = strs[i].length();
                smallestElemIndex = i;
            }else if(strs[i].length() > longestElemLength){
                longestElemLength = strs[i].length();
            }else{}
        }
        if(smallestElemLength == 0){
            return "";
        }
        
        String smallestWord = strs[smallestElemIndex];
        int beginIndex = 0;
        int endIndex = 1;
        boolean matches = false;
        String pref = smallestWord.substring(beginIndex,endIndex);
        
        while(endIndex<smallestElemLength){
            matches = matchPrefix(pref,strs);
            if(!matches){
                beginIndex++;
                endIndex++;
                pref = smallestWord.substring(beginIndex,endIndex);
            }else{
                endIndex++;
                pref = smallestWord.substring(beginIndex,endIndex);
            }
        }
        return pref;
        
    }
    
    public boolean matchPrefix(String pref, String[] strs){
        for(int j=0;j<strs.length;j++){
            if(!strs[j].contains(pref)){
                return false;
            }
        }
        return true;
    }
}