#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int levenshtein_distance(const string& s1, const string& s2) {
  int len1 = s1.size();
  int len2 = s2.size();
  // Put the shorter string first to save memory.
  if(len2 < len1)
    return levenshtein_distance(s2, s1);
  int row, col;
  // costs[i] will be the cost of editing s1.substr(0, i) to s2.substr(0, row)
  vector<int> costs(len1 + 1);
  for(col = 0; col <= len1; ++col)
    // Cost of editing s1.substr(0, col) to "" is col * deletions.
    costs[col] = col;
  // previous_costs[i] will be the cost of
  // editing s1.substr(0, i) to s2.substr(0, row-1)
  vector<int> previous_costs(len1 + 1);
  for(row = 1; row <= len2; ++row) {
    previous_costs.swap(costs);  // fast alternative to previous_costs = costs
    // Cost of editing "" to s2.subst(0, row) is row * insertions.
    costs[0] = row;
    for(col = 1; col <= len1; ++col)
      costs[col] = min(min(
          costs[col-1] + 1,  // Cost of removing the letter s1[col-1].
          previous_costs[col] + 1),  // Cost of adding the letter s2[row-1].
          previous_costs[col-1] + (   // Cost of replacing
            (s1[col-1] == s2[row-1]) ? 0 : 1));  // s1[col-1] with s2[row-1].
  }
  return costs[len1];
}