Lexicographically greater string
For given words let’s try to create first lexicographically greater string than given. Try to change only order of letters. Length of string is the same.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
import java.util.Arrays; public class Lexi { private static String sortAlfabetically(String base) { char[] chars = base.toCharArray(); Arrays.sort(chars); return String.valueOf(chars); } public String greaterThanBase(String base) { for (int iter_movingChar = base.length() - 1; iter_movingChar >= 0; iter_movingChar--) { char movingChar = base.charAt(iter_movingChar); for (int iter_charToReplacement = iter_movingChar - 1; iter_charToReplacement >= 0; iter_charToReplacement--) { char replacementLowerChar = base.charAt(iter_charToReplacement); if ((int) movingChar > (int) replacementLowerChar) { String result = ""; //return head result += base.substring(0, iter_charToReplacement); //return moved char result += movingChar; //clear tail from moved char String tail = base.substring(iter_charToReplacement); tail = tail.replaceFirst("" + movingChar, ""); //add sorted alfabetically tail result += sortAlfabetically(tail); System.out.println(base + "->" + result); return result; } } } System.out.println(base + "->" + base + " (Same string)"); return base; } public static void main(String[] args) { Lexi lexi = new Lexi(); lexi.greaterThanBase("ab");//ba lexi.greaterThanBase("abcd");//acbd lexi.greaterThanBase("dkhc");//hcdk lexi.greaterThanBase("hefg");//hegf lexi.greaterThanBase("aaa");//aaa lexi.greaterThanBase("dcba");//dcba } } |