public class CenterString {
	
  static int k;
  static String lastSolution;
  static String[] input;

  static int dist(String s1, String s2){
    int count = 0;
    for (int i=0; i<s1.length(); i++)
      if (s1.charAt(i)!=s2.charAt(i)) count++;
    return count;
  }

  public static String change(int i, String s, char t){
    char[] temp = s.toCharArray();
    temp[i] = t;
    String out = new String(temp);
    return out;
  }

  public static boolean center(String s,int l, int m){
    if (l<0) return false;
    int pos = 0;
    while (pos < k && dist(s, input[pos])<=m) pos++;
    if (pos==k){
      lastSolution=new String(s);
      return true;
    }
    if (l==0) return false;

    int[] diff = new int[m+1];
    int counter = 0;
    for (int i=0; i<s.length() && counter < m+1; i++)
      if (s.charAt(i)!=input[pos].charAt(i)) diff[counter++]=i;
      for (int i=0; i<diff.length; i++)
        if (center(change(diff[i],s,input[pos].charAt(diff[i])), l-1, m))
          return true;
      return false;
    }

  public static void main(String[] args){
    input = new String[7];
    input[0] = "TESTTEST";
    input[1] = "TESTTEXT";
    input[2] = "TEXTTEST";
    input[3] = "FESTTEXT";
    input[4] = "TEXTFEST";
    input[5] = "TESTFEST";
    input[6] = "TTSTFTST";
    k = input.length;

    boolean found = false;
    for (int m=0; !found; m++){
      found = center(input[0], m, m);
      System.out.print(m + ": " + found);
      if (found) System.out.println("  " + lastSolution);
      	else System.out.println();
    }
  }
}