Swap any num[i] and num[j] such that you return the smallest number possible.

OneSwapMinNumber.java

import java.util.Arrays;

public class OneSwapMinNumber {
  /**
   * Worst case running time
   * O(11*k) - k is the number of digits in the number (length of string)
   */
  public static String min(String num) {
    char[] digits = num.toCharArray();
    int[] rindex = new int[10];
    Arrays.fill(rindex, -1);
    for (int i = 0; i < digits.length; i++) {
      rindex[digits[i]-'0'] = i;
    }
    boolean finished = false;
    for (int i = 0; i < digits.length; i++) {
      if (finished) break;
      int found = digits[i] - '0';
      for (int j = (i==0)?1:0; j < found; j++) {
        if (rindex[j] > i) {
          char temp = digits[i];
          digits[i] = digits[rindex[j]];
          digits[rindex[j]] = temp;
          finished = true;
          break;
        }
      }
    }
    return new String(digits);
  }
}