Problem Description

Design an algorithm to reformat license keys according to specific rules. A license key consists of alphanumeric characters and dashes (-). These dashes seperate the characters into groups.

Given a required group size K, rearrange the key so that every group except possibly the first contains exactly K characters. The first group may have fewer than K characters but must contain at least one character.

For example, with input key 2-4-A0r7-4k and K=3, the reformatted result would be 24-A0R-74K.

Input Format

The first line contains the license key string with length not exceeding 1000 cahracters.

The second line contains integer K (1 ≤ K ≤ 100) representing the desired group size.

Output Format

A single line containing the reformatted license key.

Sample Input/Output

Example

Input

2-4-A0r7-4k
3

Output

24-A0R-74K

Solution Approach

Convert lowercase letters to uppercase, process the string from right to left, skip dash characters, insert a dash after every K characters, then reverse the final result.

Implemantation

Initial solution:

#include <iostream>
#include <string.h>
using namespace std;

char input_str[1005];
char temp_buffer[1005];
char result_buffer[1005];

int main()
{
    int group_size, buffer_idx = 0, result_idx = 0, counter = 0;
    
    cin >> input_str;
    cin >> group_size;
    
    int str_length = strlen(input_str);
    
    // Process from end to beginning, convert to uppercase
    for (int pos = (str_length - 1); pos >= 0; pos--) {
        if (input_str[pos] >= 'a' && input_str[pos] <= 'z') {
            input_str[pos] = input_str[pos] - 32;
        }
        if (input_str[pos] != '-') {
            temp_buffer[buffer_idx++] = input_str[pos];
        }
    }
    temp_buffer[buffer_idx] = '\0';
    
    // Build result with dashes after each K characters
    for (int pos = 0; pos < buffer_idx; pos++) {
        result_buffer[result_idx++] = temp_buffer[pos];
        counter++;
        if (counter == group_size) {
            result_buffer[result_idx++] = '-';
            counter = 0;
        }
    }
    result_buffer[result_idx] = '\0';
    
    // Print reversed result
    for (int pos = result_idx - 1; pos >= 0; pos--) {
        printf("%c", result_buffer[pos]);
    }
    return 0;
}

Improved Solution

Handle edge case where the last character might be an unwanted dash:

#include <iostream>
#include <string.h>
using namespace std;

char input_str[1005];
char temp_buffer[1005];
char result_buffer[1005];

int main()
{
    int group_size, buffer_idx = 0, result_idx = 0, counter = 0;
    
    cin >> input_str;
    cin >> group_size;
    
    int str_length = strlen(input_str);
    
    for (int pos = (str_length - 1); pos >= 0; pos--) {
        if (input_str[pos] >= 'a' && input_str[pos] <= 'z') {
            input_str[pos] = input_str[pos] - 32;
        }
        if (input_str[pos] != '-') {
            temp_buffer[buffer_idx++] = input_str[pos];
        }
    }
    temp_buffer[buffer_idx] = '\0';
    
    for (int pos = 0; pos < buffer_idx; pos++) {
        result_buffer[result_idx++] = temp_buffer[pos];
        counter++;
        if (counter == group_size) {
            result_buffer[result_idx++] = '-';
            counter = 0;
        }
    }
    result_buffer[result_idx] = '\0';
    
    // Remove trailing dash if present
    if (result_buffer[result_idx - 1] == '-') {
        result_idx--;
    }
    
    for (int pos = result_idx - 1; pos >= 0; pos--) {
        printf("%c", result_buffer[pos]);
    }
    return 0;
}

Alternative Implementation

Using string operations and STL functions:

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    string source_key, formatted_result = "";
    int target_group_size, char_count = 0;
    
    cin >> source_key >> target_group_size;
    
    for (int idx = source_key.size() - 1; idx >= 0; idx--)
    {
        if (source_key[idx] == '-')
            continue;
            
        if (source_key[idx] >= 'a' && source_key[idx] <= 'z')
            source_key[idx] -= 32;
            
        char_count++;
        formatted_result += source_key[idx];
        
        if (char_count % target_group_size == 0 && idx != 0)
        {
            char_count = 0;
            formatted_result += '-';
        }
    }
    
    reverse(formatted_result.begin(), formatted_result.end());
    cout << formatted_result;
    return 0;
}