import java.util.*;
 
class Ideone {
	public static void main(String[] args){
		String s1 = "SATURDAY";
		String s2 = "SUNDAY";
 
		int[][] dist = new int[s1.length()+1][s2.length()+1];
 
		//Initialize first row and first column
		for(int i=0; i<=s1.length();i++){
			dist[i][0] = i;
		}
		for(int i=0; i<=s2.length(); i++){
			dist[0][i] = i;	
		}
 
		for(int i=1; i<=s1.length();i++){
			for(int j=1; j<=s2.length();j++){
				dist[i][j] = min(dist[i-1][j]+1, dist[i][j-1]+1, dist[i-1][j-1]+(s1.charAt(i-1) == s2.charAt(j-1) ? 0 : 1));		
			}
		}
 
		System.out.println("Edit distance => "+ dist[s1.length()][s2.length()]);
	}
 
	private static int min(int a, int b, int c){
		if(a <= b && a <= c) return a;
		else if(b<=a && b<=c) return b;
		else return c;
	}
}