Java - Circular arrangement of letters
Intuition\n Describe your first thoughts on how to solve this problem. \nIt is clear as soon as the problem is seen that each character has to be calculated unt
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIt is clear as soon as the problem is seen that each character has to be calculated until the \'k\' is totally used up. So, for each character the smallest possible character within \'k\' distance has to be found.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe approach is for each character compute the smallest character in k reach. \n\nIt is important to identify the condition that each letter could find its next smallest character not just in the forward direction but in backward direction as well. \nEx. for character \'z\', the smallest character in reach with distance greater than 0 is \'a\' (considering the characters are in a circular form)\n\n........ - \'y\' - \'z\' - \'a\' - \'b\' - \'c\' - \'d\' - ...... - \'x\' - \'y\' - \'z\' - \'a\' - \'b\' - ......\n\nSo, we compute both the forward smallest character and backward smallest character and their respective distances. \n\nThen we have 3 conditions:\n1. Smallest Character is the character found in forward direction, return it.\n2. Smallest Character is the character found in backward direction, return it.\n3. Smallest Character is the same in both directions, compare their forward and backward distances and use the smallest distance.\n\nHave a globalK to keep track of the remaining k that can be used up.\n# Complexity\n- Time complexity: O(n) \n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n) \n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n# Code\n```\nclass Solution {\n    int globalK = 0;\n    int distf = 0;\n    int distb = 0;\n    public String getSmallestString(String s, int k) {\n        globalK = k;\n        StringBuilder strb = new StringBuilder();\n        for(char c: s.toCharArray()){\n            if(globalK==0){\n                strb.append(c);\n                continue;\n            }\n            char x = smallestChar(c, globalK);\n            strb.append(x);\n        }\n        return strb.toString();\n    }\n\n    char smallestChar(char c, int k){\n        char fwd = smallestCharInFwd(c, k);\n        char bwd = smallestCharInBwd(c, k);\n        if(fwd < bwd){\n            globalK -= distf;\n            // System.out.println("1"+fwd+" "+distf);\n            return fwd;\n        }else if(bwd < fwd){\n            globalK -= distb;\n            // System.out.println("2"+bwd+" "+distb);\n            return bwd;\n        }else if(distf < distb){\n            globalK -= distf;\n            // System.out.println("1"+fwd+" "+distf);\n            return fwd;\n        }else{\n            globalK -= distb;\n            // System.out.println("2"+bwd+" "+distb);\n            return bwd;\n        }\n    }\n\n    char smallestCharInFwd(char c, int k){\n        if((c-\'a\')<=k){ \n            distf = c-\'a\';\n            return \'a\';\n        }\n        else{ \n            distf = k;\n            return (char)(c-k);\n        }\n    }\n\n    char smallestCharInBwd(char c, int k){\n        if((\'z\'-c)<k){ \n            distb = (int)(\'z\'-c)+1;\n            return \'a\';\n        }\n        else{\n            distb = k;\n            return (char)(c+k);\n        }\n    }\n}\n```
['Java']