CodeEval - Play with DNA - Hard

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws FileNotFoundException, IOException {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb=new StringBuffer();
        String line;
        while ((line = in.readLine()) != null) {
            StringTokenizer st=new StringTokenizer(line);
            String pattern=st.nextToken();
            int allowedMiss=Integer.parseInt(st.nextToken());
            String str=st.nextToken();
            LinkedList<Pattern> list=new LinkedList<Pattern>();
            StringBuilder strb=new StringBuilder();
            for(int i=0;i<pattern.length()-1;i++){
                strb.append(str.charAt(i));
            }
            for(int i=pattern.length()-1;i<str.length();i++){
                 strb.append(str.charAt(i));
                 int dist=levenshteinDistance(pattern, strb.toString());
                 if(dist<=allowedMiss){
                     list.add(new Pattern(dist, strb.toString()));
                 }
                 strb.deleteCharAt(0);
            }
            Collections.sort(list);
            boolean first=true;
            while(!list.isEmpty()){
                if(!first){
                    sb.append(' ');
                }
                sb.append(list.remove().getPattern());
                first=false;
            }
            if(first){
                sb.append("No match");
            }
            sb.append('\n');
        }
       
        System.out.print(sb);
    }
   
    private static int minimum(int a, int b, int c) {
        return Math.min(Math.min(a, b), c);
    }

    public static int levenshteinDistance(String str1,String str2) {
        int[][] distance = new int[str1.length() + 1][str2.length() + 1];

        for (int i = 0; i <= str1.length(); i++)
            distance[i][0] = i;
        for (int j = 1; j <= str2.length(); j++)
            distance[0][j] = j;

        for (int i = 1; i <= str1.length(); i++)
            for (int j = 1; j <= str2.length(); j++)
                distance[i][j] = minimum(
                        distance[i - 1][j] + 1,
                        distance[i][j - 1] + 1,
                        distance[i - 1][j - 1]+ ((str1.charAt(i - 1) == str2.charAt(j - 1)) ? 0 : 1));

        return distance[str1.length()][str2.length()];   
    }

}
class Pattern implements Comparable<Pattern> {
    int score;
    String pattern;

    public Pattern(int score, String pattern) {
        this.score = score;
        this.pattern = pattern;
    }
   

    public String getPattern() {
        return pattern;
    }

    public int getScore() {
        return score;
    }

    public void setPattern(String pattern) {
        this.pattern = pattern;
    }

    public void setScore(int score) {
        this.score = score;
    }

    @Override
    public int compareTo(Pattern o) {
        if(this.score<o.getScore())
            return -1;
        if(this.score>o.getScore())
            return 1;
        return this.pattern.compareTo(o.getPattern());
    }
   
   
}