Skip to content

3106. Lexicographically Smallest String After Operations With Constraint 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  string getSmallestString(string s, int k) {
    string ans = s;

    for (char& c : ans) {
      if (k == 0)
        break;
      const int distToA = min(c - 'a', 'z' - c + 1);
      if (k >= distToA) {
        k -= distToA;
        c = 'a';
      } else {
        // k is not enough to change the current letter to 'a', so move as
        // closer to 'a' as possible.
        c -= k;
        k = 0;
      }
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public String getSmallestString(String s, int k) {
    StringBuilder sb = new StringBuilder(s);

    for (int i = 0; i < sb.length(); ++i) {
      if (k == 0)
        break;
      final int distToA = Math.min(sb.charAt(i) - 'a', 'z' - sb.charAt(i) + 1);
      if (k >= distToA) {
        k -= distToA;
        sb.setCharAt(i, 'a');
      } else {
        // k is not enough to change the current letter to 'a', so move as
        // closer to 'a' as possible.
        sb.setCharAt(i, (char) (sb.charAt(i) - k));
        k = 0;
      }
    }

    return sb.toString();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def getSmallestString(self, s: str, k: int) -> str:
    ans = list(s)

    for i, c in enumerate(s):
      if k == 0:
        break
      distToA = min(string.ascii_lowercase.index(c), ord('z') - ord(c) + 1)
      if k >= distToA:
        k -= distToA
        ans[i] = 'a'
      else:
        # k is not enough to change the current letter to 'a', so move as closer
        # to 'a' as possible.
        ans[i] = chr(ord(c) - k)
        k = 0

    return ''.join(ans)