Untitled

public class Solution {

    public static String getSpecialString(String s) {
        int n = s.length();
        char[] t = new char[n];
        boolean greater = false;

        for (int i = 0; i < n; i++) {
            char startChar = (!greater) ? s.charAt(i) : 'a';
            boolean found = false;

            for (char ch = startChar; ch <= 'z'; ch++) {
                if (i > 0 && ch == t[i - 1]) {
                    continue;
                }
                if (!greater && ch < s.charAt(i)) {
                    continue;
                }
                if (!greater && ch > s.charAt(i)) {
                    greater = true;
                }
                t[i] = ch;

                // Compare t[0..i] with s[0..i]
                int cmp = compareArrays(t, s.toCharArray(), i);
                if (cmp > 0) {
                    greater = true;
                    found = true;
                    break;
                } else if (cmp == 0) {
                    found = true;
                    // If we are at the last character and haven't increased, try the next character
                    if (i == n - 1 && !greater) {
                        found = false;
                        continue;
                    }
                    break;
                } else {
                    // t[0..i] is less than s[0..i], try the next character
                    continue;
                }
            }

            if (!found) {
                // Backtracking to find the next valid character
                while (i > 0) {
                    i--;
                    char prevCh = t[i];
                    boolean innerFound = false;

                    for (char ch = (char) (prevCh + 1); ch <= 'z'; ch++) {
                        if (i > 0 && ch == t[i - 1]) {
                            continue;
                        }
                        if (ch > s.charAt(i)) {
                            greater = true;
                        } else if (ch < s.charAt(i)) {
                            continue;
                        }
                        t[i] = ch;
                        innerFound = true;
                        break;
                    }

                    if (innerFound) {
                        i++;
                        // Fill the rest of the string
                        for (; i < n; i++) {
                            boolean charFound = false;
                            for (char ch = 'a'; ch <= 'z'; ch++) {
                                if (i > 0 && ch == t[i - 1]) {
                                    continue;
                                }
                                t[i] = ch;
                                charFound = true;
                                break;
                            }
                            if (!charFound) {
                                return "-1";
                            }
                        }
                        String result = new String(t);
                        return (result.compareTo(s) > 0) ? result : "-1";
                    }
                }
                return "-1";
            }
        }

        String result = new String(t);
        return (result.compareTo(s) > 0) ? result : "-1";
    }

    private static int compareArrays(char[] t, char[] s, int end) {
        for (int i = 0; i <= end; i++) {
            if (t[i] != s[i]) {
                return t[i] - s[i];
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        // Test cases:

        String s1 = "abccde";
        System.out.println(getSpecialString(s1));  // Output: abccdf

        String s2 = "zzab";
        System.out.println(getSpecialString(s2));  // Output: zzac

        String s3 = "abbd";
        System.out.println(getSpecialString(s3));  // Output: abca

        String s4 = "abcdd";
        System.out.println(getSpecialString(s4));  // Output: "abcdh"

        String s5 = "zzzz";
        System.out.println(getSpecialString(s5));  // Output: "-1"

        String s6 = "ba";
        System.out.println(getSpecialString(s6));  // Output: "bc"

        String s7 = "aabbcc";
        System.out.println(getSpecialString(s7));  // Output: "aabbcd"

        String s8 = "zyx";
        System.out.println(getSpecialString(s8));  // Output: "-1"

        String s9 = "abcxyz";
        System.out.println(getSpecialString(s9));  // Output: "abcyza"

        String s10 = "aa";
        System.out.println(getSpecialString(s10));  // Output: "ab"

        String s11 = "zz";
        System.out.println(getSpecialString(s11));  // Output: "-1"
    }
}