3106. Lexicographically Smallest String After Operations With Constraint

MediumGreedyString

Problem Description

You are given a string s and an integer k. The task is to create a function distance(s1, s2) which calculates the sum of the minimum distances between characters at the same positions in two strings s1 and s2 of equal length. These characters are in cyclic order from 'a' to 'z'.

For example:

distance("ab", "cd") results in 4.
distance("a", "z") results in 1.

Your goal is to modify the string s to form a new string t such that the distance between s and t is at most k and t is the lexicographically smallest string possible.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To solve the problem, we start by iterating through each character in the string s. For each character, we attempt to change it to any smaller letter ranging from 'a' up to just before the current character. The distance d for changing from character c1 to a candidate character c2 is calculated as the minimum of moving forward and moving backward in the cyclic order.

If changing to c2 requires a distance d that can be covered by the remaining k, we perform the change, subtract d from k, and move to the next character in the string. This greedy approach ensures that we always try to make the lexicographically smallest changes while keeping within the allowed distance k.

This method ensures the resulting string is the lexicographically smallest possible while adhering to the given distance constraint.

Learn more about Greedy patterns.

Solution Approach

The solution employs a greedy algorithm to solve the problem. Here is a step-by-step explanation of the implementation:

Convert the string s into a list of characters cs so we can modify it easily.
Iterate over each character c1 in s, with its index i.
For each character c1, we aim to make it as small as possible while keeping the string lexicographically smaller. To achieve this, enumerate all characters c2 from 'a' up to, but not including, c1.
Calculate the cyclic distance d between c1 and c2. This is done using:
- d = min(ord(c1) - ord(c2), 26 - ord(c1) + ord(c2))
- Here, ord() gives the ASCII value of a character. We consider both the forward and backward paths in the cycle.
If d (the cost to change c1 to c2) is less than or equal to k, then:
- Change the i-th character in cs to c2.
- Subtract d from k since we've used up d of our allowed distance budget.
Break the inner loop once a change is made to move to the next character, as we want to make the smallest possible change first.
After completing the traversal of the string, join the modified list cs back into a string to form the result.
Return the resulting string, which is the lexicographically smallest string that satisfies the distance constraint.

By following this approach, we ensure that each character's change is minimized first, thus making the overall string the smallest possible while considering the distance constraint k.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example using the string s = "bdc" and k = 3. The goal is to transform s into the lexicographically smallest string t such that the distance between s and t is at most k.

Initialization: Convert s into a list of characters cs = ['b', 'd', 'c'].
Iteration Over Each Character in s:
- Position 0: Character 'b':
  - Attempt to change 'b' to smaller lexicographically characters starting from 'a':
    - c2 = 'a'
      - Calculate the cyclic distance d:
        
        d = min(ord('b') - ord('a'), 26 - (ord('b') - ord('a'))) = min(1, 25) = 1
      - Since d = 1 <= k = 3, we change 'b' to 'a'. Now, cs = ['a', 'd', 'c'] and k = 3 - 1 = 2.
- Position 1: Character 'd':
  - Attempt to change 'd' to smaller lexicographically characters starting from 'a':
    - c2 = 'a'
      - Calculate the cyclic distance d:
        
        d = min(ord('d') - ord('a'), 26 - (ord('d') - ord('a'))) = min(3, 23) = 3
      - Since d = 3 <= k = 2 doesn't hold, we can't proceed to change 'd' to 'a'.
    - c2 = 'c'
      - Calculate the cyclic distance d:
        
        d = min(ord('d') - ord('c'), 26 - (ord('d') - ord('c'))) = min(1, 25) = 1
      - Since d = 1 <= k = 2, we change 'd' to 'c'. Now, cs = ['a', 'c', 'c'] and k = 2 - 1 = 1.
- Position 2: Character 'c':
  - Attempt to change 'c' to smaller lexicographical characters starting from 'a':
    - c2 = 'a'
      - Calculate the cyclic distance d:
        
        d = min(ord('c') - ord('a'), 26 - (ord('c') - ord('a'))) = min(2, 24) = 2
      - Since d = 2 <= k = 1 doesn't hold, we cannot make a change here.
Result Construction: Join the list cs back into a string. The resulting string is t = "acc".

Following this process, we transformed s into "acc", which is the lexicographically smallest string possible given the distance constraint k = 3.

Solution Implementation

1from string import ascii_lowercase
2
3class Solution:
4    def getSmallestString(self, s: str, k: int) -> str:
5        # Convert the input string to a list of characters
6        characters = list(s)
7      
8        # Iterate over each character in the string
9        for i, char_current in enumerate(s):
10            # Iterate over each character in the lowercase alphabet
11            for char_new in ascii_lowercase:
12                # If the new character is not smaller, break out of the loop
13                if char_new >= char_current:
14                    break
15                # Calculate the distance to convert current character to the new character
16                distance = min(ord(char_current) - ord(char_new), 
17                               26 - ord(char_current) + ord(char_new))
18                # Check if the available k can cover the cost
19                if distance <= k:
20                    # Replace the character with the new character
21                    characters[i] = char_new
22                    # Decrement k by the distance cost
23                    k -= distance
24                    break  # Break since the character has been updated
25                  
26        # Return the joined list of characters as a string
27        return "".join(characters)
28

1class Solution {
2    public String getSmallestString(String s, int k) {
3        // Convert the input string to a character array for easier manipulation
4        char[] charArray = s.toCharArray();
5      
6        // Iterate through each character in the array
7        for (int i = 0; i < charArray.length; ++i) {
8            char currentChar = charArray[i];
9          
10            // Try to replace currentChar with a smaller character
11            for (char possibleChar = 'a'; possibleChar < currentChar; ++possibleChar) {
12                // Calculate the difference in alphabet positions between currentChar and possibleChar
13                int distance = Math.min(currentChar - possibleChar, 26 - currentChar + possibleChar);
14              
15                // If the difference is less than or equal to the remaining "budget" k
16                if (distance <= k) {
17                    // Replace the current character with the smaller one
18                    charArray[i] = possibleChar;
19                    // Deduct the distance from the budget k
20                    k -= distance;
21                    // Exit the inner loop to move to the next character
22                    break;
23                }
24            }
25        }
26      
27        // Convert the modified character array back to a string and return
28        return new String(charArray);
29    }
30}
31

1#include <string>
2#include <algorithm>
3using namespace std;
4
5class Solution {
6public:
7    string getSmallestString(string s, int k) {
8        // Iterate over each character in the string
9        for (int i = 0; i < s.size(); ++i) {
10            char currentChar = s[i];
11            // Try changing currentChar to a smaller character
12            for (char newChar = 'a'; newChar < currentChar; ++newChar) {
13                // Calculate the distance to change currentChar to newChar
14                int distance = min(currentChar - newChar, 26 - currentChar + newChar);
15                // Check if it's possible to change the character within the remaining operations
16                if (distance <= k) {
17                    s[i] = newChar; // Update the character
18                    k -= distance; // Decrease the remaining operations by the distance
19                    break; // Break after the first valid change
20                }
21            }
22        }
23        return s; // Return the modified string
24    }
25};
26

1// This function modifies the input string 's' by decreasing the character values
2// within the limit 'k' to create the lexicographically smallest possible string
3function getSmallestString(s: string, k: number): string {
4    // Convert the input string 's' into an array of characters
5    const charArray: string[] = s.split('');
6
7    // Iterate over each character in the string 's'
8    for (let i = 0; i < s.length; ++i) {
9        // Iterate over all ASCII values from 97 ('a') to the ASCII value of the current character
10        for (let j = 97; j < s[i].charCodeAt(0); ++j) {
11            // Calculate the cost 'd' to replace the current character with one having ASCII value 'j'
12            const cost = Math.min(s[i].charCodeAt(0) - j, 26 - (s[i].charCodeAt(0) - j));
13          
14            // Check if the cost 'd' is within the available limit 'k'
15            if (cost <= k) {
16                // Replace the character at position 'i' with the new character
17                charArray[i] = String.fromCharCode(j);
18              
19                // Reduce the limit 'k' by the cost of this operation
20                k -= cost;
21              
22                // Exit the inner loop as we've modified the current character
23                break;
24            }
25        }
26    }
27  
28    // Join the modified character array into a string and return it
29    return charArray.join('');
30}
31

Time and Space Complexity

The time complexity of the code is O(n × 26), which simplifies to O(n), where n is the length of the string s. This is because for each character in the string, a loop over a constant set of 26 lowercase letters is performed, resulting in the overall complexity of O(n).

The space complexity is O(n). This arises from storing the modified list of characters cs, which is directly proportional to the size of the input string s.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan: