License Key Formatting Leetcode Solution

Difficulty Level Easy
Frequently asked in Capital One Google
algorithms coding Interview interviewprep LeetCode LeetCodeSolutions String StringBuilderViews 4439

Problem Statement

In the problem “License Key Formatting”, the input consists of a string of characters, representing a license key. Initially, the string is separated into N + 1 groups(words) by N dashes in between. We are also given an integer K, and the goal is to format the string such that every group contains exactly K characters, except for the first one, which is allowed to characters less than K. Furthermore, the groups must be separated by ‘-‘(dash) and have only uppercase letters.

Example

S = "5F3Z-2e-9-w", K = 4
5F3Z-2E9W
S = "2-5g-3-J", K = 2
2-5G-3J

Approach

It is intuitive that we should create a new string while iterating backward in string s(input). This is important because we know except for the first group, all other groups must have exactly ‘k’ letters in them. If we iterate back in string s, we can maintain a counter that keeps a count of the number of characters added in a group. If it becomes equal to ‘k’ at any moment, we can reset it back to zero. This way we keep adding the elements in the new string and before returning it, we reverse it for regaining the order.

Implementation of License Key Formatting Leetcode Solution

C++ Program

#include <bits/stdc++.h>

using namespace std;

string licenseKeyFormatting(string s , int k) {
    string ans;
    int cnt = 0 , n = s.size();

    for(int i = n - 1 ; i >= 0 ; i--) {
        if(s[i] != '-') {
            if(cnt == k) {
                ans += '-';
                cnt = 0;
            }
            cnt++;
            if(s[i] >= 'a' && s[i] <= 'z') {
                s[i] += 'A' - 'a';
            }
            ans += s[i];
        }
    }

    reverse(ans.begin() , ans.end());
    return ans;
}

int main() {
    string s = "5F3Z-2e-9-w";
    int K = 4;
    cout << licenseKeyFormatting(s, K) << endl;
    return 0;
}

Java Program

import java.lang.*;
import java.io.*;
import java.util.*;

class license_key {
    public static void main(String args[]) {
        String s = "5F3Z-2e-9-w";
        int K = 4;
        System.out.println(licenseKeyFormatting(s , K));
    }

    public static String licenseKeyFormatting(String s , int k) {
        StringBuilder ans = new StringBuilder();
        int cnt = 0 , n = s.length();

        char c;
        for(int i = n - 1 ; i >= 0 ; i--) {
            c = s.charAt(i);
            if(c != '-') {
                if(cnt == k) {
                    ans.append('-');
                    cnt = 0;
                }
                cnt++;
                if(c >= 'a' && c <= 'z') {
                    c += 'A' - 'a';
                }
                ans.append(c);
            }
        }
        return ans.reverse().toString();
    }
}

5F3Z-2E9W

Complexity Analysis of License Key Formatting Leetcode Solution

Time Complexity

O(N), N = length of the string. The program is linear as we iterate the string once.

Space Complexity 

O(1), as we use constant memory space.

Translate »