[Google Interview] License Key Formatting

[toc]

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.

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))

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

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:

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.

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.

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.