The smallest string

You are given a string $S$ which consists of lower case Latin letters and you need to perform the following operation exactly $K$ times:

• Select any character and replace it with its next character ['a' with 'b', 'b' with 'c'.... 'z' with 'a'].

You need to find the lexicographically smallest string after performing exactly $K$ operations on string $S$.

Example:

Input:  n=3, k=3, str="zya"
Output: aaa

Approach

Java

import java.util.Arrays;
import java.util.Objects;

public class TheSmallestString {
    public static long MOD = 998244353;
    static long[] dp;

    public static void main(String[] args) {
        int MAX = 26;
        int n = 3;
        int k = 3;
        String str = "zya";
        char[] data = str.toCharArray();
        for (int i = 0; i < n; i++) {
            int cur = data[i] - 'a';
            int need = (MAX - cur) % MAX;
            if (need > k || (i + 1) == n) {
                if (i + 1 == n) {
                    int v = (cur + k) % MAX;
                    data[i] = (char) (v + 'a');
                }
            } else {
                k -= need;
                data[i] = 'a';
            }
        }
        System.out.println(new String(data));
    }

    public static int[] KMP(String val) {
        int i = 0;
        int j = -1;
        int[] result = new int[val.length() + 1];
        result[0] = -1;
        while (i < val.length()) {
            while (j >= 0 && val.charAt(j) != val.charAt(i)) {
                j = result[j];
            }
            j++;
            i++;
            result[i] = j;
        }
        return result;

    }

    public static boolean nextPer(int[] data) {
        int i = data.length - 1;
        while (i > 0 && data[i] < data[i - 1]) {
            i--;
        }
        if (i == 0) {
            return false;
        }
        int j = data.length - 1;
        while (data[j] < data[i - 1]) {
            j--;
        }
        int temp = data[i - 1];
        data[i - 1] = data[j];
        data[j] = temp;
        Arrays.sort(data, i, data.length);
        return true;
    }

    public static int digit(long n) {
        int result = 0;
        while (n > 0) {
            n /= 10;
            result++;
        }
        return result;
    }

    public static double dist(long a, long b, long x, long y) {
        double val = (b - a) * (b - a) + (x - y) * (x - y);
        val = Math.sqrt(val);
        double other = x * x + a * a;
        other = Math.sqrt(other);
        return val + other;

    }

    public static class Point implements Comparable<Point> {

        int x;
        int y;

        public Point(int start, int end) {
            this.x = start;
            this.y = end;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            Point point = (Point) o;
            return x == point.x && y == point.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

        @Override
        public int compareTo(Point o) {
            return Integer.compare(x, o.x);
        }
    }

    public static class FT {

        long[] data;

        FT(int n) {
            data = new long[n];
        }

        public void update(int index, long value) {
            while (index < data.length) {
                data[index] += value;
                index += (index & (-index));
            }
        }

        public long get(int index) {
            long result = 0;
            while (index > 0) {
                result += data[index];
                index -= (index & (-index));
            }
            return result;

        }
    }

    public static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    public static long pow(long a, long b) {
        if (b == 0) {
            return 1;
        }
        if (b == 1) {
            return a;
        }

        long val = pow(a, b / 2);
        if (b % 2 == 0) {
            return (val * val) % MOD;
        } else {
            return (val * ((val * a) % MOD)) % MOD;

        }
    }

}