[Google Interview] License Key Formatting

Company tags: Google, Capital One

Problem Formulation

You are given a license key represented as a string s that consists of only alphanumeric characters and dashes. The string is separated into n + 1 groups by n dashes. You are also given an integer k.

We want to reformat the string s such that each group contains exactly k characters, except for the first group, which could be shorter than “k” but still must contain at least one character. Furthermore, there must be a dash inserted between two groups, and you should convert all lowercase letters to uppercase.

Return the reformatted license key.

Constraints:

  • 1 <= s.length <= 105
  • s consists of English letters, digits, and dashes '-'.
  • 1 <= k <= 104

Examples

Let’s have a look at some examples to improve our understanding of this problem.

Example 1:
Input: s = “5F3Z-2e-9-w”, k = 4
Output: “5F3Z-2E9W”
Explanation: The string s has been split into two parts, each part has 4 characters. The two extra dashes are not needed and can be removed.

Example 2:
Input: s = “2-5g-3-J”, k = 2
Output: “2-5G-3J”
Explanation: The string s has been split into three parts, each part has 2 characters except the first part as it could be shorter as mentioned above.

Example 3:
Input: s = “3hj78k”, k = 5
Output: “3-HJ78K”
Explanation: The string s has been split into two parts, the last part has 5 characters and the first part is shorter. 

Example 4:
Input: s = “a-bc”, k = 3
Output: “ABC”
Explanation: The extra dashes can be removed.

Now that you have a clear understanding of the problem, let’s dive into the solution:

Method 1: Reversing The String

Approach: We know that only the first part could be shorter and all the other parts must have k characters. Hence, we can start iterating from the end of the string.  Add the string in another array. You need to add the characters by converting them to uppercase in the resultant array. When k characters are already added to the string, append a dash “-” to the string. Finally, reverse the string to get the original order to return the final output.

Let’s look at the solution to understand this:

def license_key(s, k):
    res = []
    # traverse through the reversed string
    for i in reversed(range(len(s))):
        # skip dashes present in original/given string
        if s[i] == '-':
            continue
        # inserting dash as soon as k characters have been appended to res
        if len(res) % (k + 1) == k:
            res += '-'
        # convert each character to uppercase
        res += s[i].upper()
    # return final string after reversing the contents of the res variable
    return "".join(reversed(res))

Here’s a quick recap of functions used in the above code:

str.join(iterable) : Concatenates the elements in an iterable. The result is a string whereas each elements in the iterable are “glued together” using the string on which it is called as a delimiter.

➡ Python’s built-in reversed(sequence) function returns a reverse iterator over the values of the given sequence such as a list, a tuple, or a string.

Test-Case Analysis: Let’s run this solution on our examples.

# Example 1   
s = “5F3Z-2e-9-w”
k = 4
print(license_key(s, k))
# 5F3Z-2E9W

# Example 2
s = “2-5g-3-J”
k = 2
print(license_key(s, k))
# 2-5G-3J

# Example 3
s = “3hj78k”
k = 5
print(license_key(s, k))
# 3-HJ78K

# Example 4
s = “a-bc”
k = 3
print(license_key(s, k))
# ABC

Hurrah! It passed all the test cases.

Complexity Analysis:

  • Time Complexity: As you have to traverse through the string linearly only once, the time complexity of this method is O(n).
  • Space Complexity: The space complexity of this method is O(1) as constant memory space has been used.

Method 2: Using Deque

A gentle Introduction to the deque container of the collections library in Python:

Deque() in Python: A deque (double-ended queue) is a part of the collections library in Python and is used to add and remove elements from either end. The module has different methods which can be invoked directly by passing required arguments. 

Here’s a quick overview of the operations that you can perform using deque:
append(): inserts the value to the right end of the deque.
appendleft(): inserts the value to the left end of the deque.
pop(): deletes an argument from the right end of the deque.
popleft(): deletes an argument from the left end of the deque.

Some other notable operations of deque: index(), insert(), remove(), count(), extend(), extendleft(), reverse(), rotate(). Please feel free to dive into the deque objects at the official link for more information.

➼ A deque performs faster append and pop operations as compared to a list in Python as it has a time complexity of O(1) as compared to a list which has the runtime complexity of O(n).

Note: You have to import the deque container from the collections module before utilizing it.

Approach: In this approach, we will store each character of the given string from the left end in a container (deque). However, we will eliminate the dashes and won’t store them in the container. We also need to keep track of the given value “k” with the help of a counter variable in order to place the dashes in the output string. Thus, everytime the value of the counter is equal to the value of ‘k‘ , we will simply append the dash ‘-‘ to our container which stores the output string. Also, while traversing through each character of the given string we have to convert it to uppercase before appending it to the deque container if it represents an alphabet. In case it is a number, we simply append it to the container as it is. Once all the characters along with the dashes have been arranged in the proper index of the container, we have to pop/extract each element from the left end of the deque (container) one by one and then convert it to a string with the help of the join() method to generate the final output.

Let’s have a look at the following illustration to understand the above approach:

Algorithm:

  1. Initialize a variable “c” to store the count of characters in the given string.
  2. Check for the end condition and check for the boundary condition: the end character must not be “-
  3. Append the character to the left end of the deque after converting it into uppercase. Increment the value of count.
  4. If the count becomes equal to k, update the value of c as 0 and append “-” to the string.
  5. Finally, return the string with the help of the join() method.

Solution:

from collections import deque


def license_key(s, k):
    q = deque()
    end = len(s) - 1
    c = 0
    while end >= 0:
        if s[end] == '-':
            end = end - 1
            continue
        if not s[end].isalpha():
            q.appendleft(s[end])
        else:
            q.appendleft(s[end].upper())
        c += 1
        if c == k:
            c = 0
            q.appendleft('-')
        end -= 1
    if q and q[0] == '-':
        q.popleft()

    return ''.join(q)

Test-Case Analysis: Let’s run this solution on our examples.

# Example 1   
s = “5F3Z-2e-9-w”
k = 4
print(license_key(s, k))
# 5F3Z-2E9W

# Example 2
s = “2-5g-3-J”
k = 2
print(license_key(s, k))
# 2-5G-3J

# Example 3
s = “3hj78k”
k = 5
print(license_key(s, k))
# 3-HJ78K

# Example 4
s = “a-bc”
k = 3
print(license_key(s, k))
# ABC

Yeah! It passed all the test cases.

Complexity Analysis:

  • Time Complexity: As deque() functions operate in O(1) time and you have to traverse the string only once, thus this approach has a linear time complexity, i.e. O(n).
  • Space Complexity: The space complexity of this method is O(1) as no extra space has been used.

Method 3: Using a List

Approach: In this approach, you have to use a list that will initially store the uppercase characters of the original string. Further, check if the length of the stack is greater than the given value ‘k‘.  If yes, append the value to a variable ‘res‘ by popping the stack ‘k times. Append “-“. If not, append the value to res by popping the stack len(st) times. Append “-“. Finally, return the reversed string.

Note: Store the res value till the second-last character of the string as the last character will always be “-“.

Solution:

def license_key(s, k):
    st = [c.upper() for c in s if c!= "-"]
    res = ""
    while st:
        if len(st) >= k:
            for i in range(k):
                res = res + st.pop()
            res = res + "-"
        else:
            for i in range(len(st)):
                res = res + st.pop()
            res = res + "-"
    res = res[:-1]
    return ''.join(res[::-1])

Test-Case Analysis: Let’s run this solution on our examples.

# Example 1   
s = “5F3Z-2e-9-w”
k = 4
print(license_key(s, k))
# 5F3Z-2E9W

# Example 2
s = “2-5g-3-J”
k = 2
print(license_key(s, k))
# 2-5G-3J

# Example 3
s = “3hj78k”
k = 5
print(license_key(s, k))
# 3-HJ78K

# Example 4
s = “a-bc”
k = 3
print(license_key(s, k))
# ABC

Complexity Analysis: As we have traversed the string only once, the time complexity of this method is O(n).

Conclusion

I hope you enjoyed this coding interview question. Please stay tuned and subscribe for more interesting coding problems.

Post Credits: Rashi Agarwal and Shubham Sayon


Recommended: Finxter Computer Science Academy

  • One of the most sought-after skills on Fiverr and Upwork is web scraping. Make no mistake: extracting data programmatically from websites is a critical life skill in today’s world that’s shaped by the web and remote work.
  • So, do you want to master the art of web scraping using Python’s BeautifulSoup?
  • If the answer is yes – this course will take you from beginner to expert in Web Scraping.