Making File Names Unique - Practice Coding Problems

Making File Names Unique - Problem

Given an array of strings names of size n. You will create n folders in your file system such that, at the i^th minute, you will create a folder with the name names[i].

Since two files cannot have the same name, if you enter a folder name that was previously used, the system will have a suffix addition to its name in the form of (k), where k is the smallest positive integer such that the obtained name remains unique.

Return an array of strings of length n where ans[i] is the actual name the system will assign to the i^th folder when you create it.

Input & Output

Example 1 — Basic Duplicates

$ Input: names = ["pes","fifa","gta","pes(2023)"]

› Output: ["pes","fifa","gta","pes(2023)"]

💡 Note: All names are unique, so no modifications needed. The system assigns exact names as requested.

Example 2 — Multiple Duplicates

$ Input: names = ["gta","gta(1)","gta","avalon"]

› Output: ["gta","gta(1)","gta(2)","avalon"]

💡 Note: First 'gta' is unique. 'gta(1)' is unique. Second 'gta' conflicts with first, so becomes 'gta(2)' (since 'gta(1)' exists). 'avalon' is unique.

Example 3 — Sequential Conflicts

$ Input: names = ["kaido","kaido(1)","kaido","kaido(1)"]

› Output: ["kaido","kaido(1)","kaido(2)","kaido(1)(1)"]

💡 Note: First 'kaido' is unique. 'kaido(1)' is unique. Second 'kaido' becomes 'kaido(2)'. Second 'kaido(1)' becomes 'kaido(1)(1)'.

Constraints

1 ≤ names.length ≤ 5 × 10⁴
1 ≤ names[i].length ≤ 20
names[i] consists of lower case English letters, digits, and/or round brackets.

Visualization

Tap to expand

Understanding the Visualization

Input

Array of requested file names

Process

Add suffix (k) to duplicates where k is smallest available

Output

Array of actual unique file names

Key Takeaway

🎯 Key Insight: Use a hash map to track the next available suffix number for each base name, avoiding redundant conflict checks

Asked in

a Amazon 15 f Facebook 12

The key insight is to track each name's next available suffix using a hash map. When we encounter a duplicate, we use the stored suffix number and increment it for future duplicates. Best approach uses hash map tracking for O(1) lookups. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map - Track Used Names	O(n)	O(n)	Use hash map to track used names and their next available suffix number
Brute Force - Linear Search	O(n²)	O(n)	For each name, check all previous names to find conflicts and increment suffix until unique

Hash Map - Track Used Names — Algorithm Steps

Create hash map to track name counts
For each name, check if it exists in map
If not exists, add to result and mark as used
If exists, append current suffix number and increment counter

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Hash Map

Look up name in hash map

First Time

If not found, add to result and mark as used

Duplicate Found

Use stored suffix number and increment counter

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NAMES 1000
#define MAX_NAME_LEN 1000

typedef struct {
    char name[MAX_NAME_LEN];
    int count;
} NameCount;

char** solution(char** names, int namesSize, int* returnSize) {
    NameCount used[MAX_NAMES];
    int usedSize = 0;
    char** result = malloc(namesSize * sizeof(char*));
    *returnSize = 0;
    
    for (int i = 0; i < namesSize; i++) {
        int found = -1;
        for (int j = 0; j < usedSize; j++) {
            if (strcmp(used[j].name, names[i]) == 0) {
                found = j;
                break;
            }
        }
        
        if (found == -1) {
            strcpy(used[usedSize].name, names[i]);
            used[usedSize].count = 1;
            usedSize++;
            result[*returnSize] = malloc(strlen(names[i]) + 1);
            strcpy(result[*returnSize], names[i]);
            (*returnSize)++;
        } else {
            int suffix = used[found].count;
            char newName[MAX_NAME_LEN];
            sprintf(newName, "%s(%d)", names[i], suffix);
            used[found].count++;
            
            strcpy(used[usedSize].name, newName);
            used[usedSize].count = 1;
            usedSize++;
            
            result[*returnSize] = malloc(strlen(newName) + 1);
            strcpy(result[*returnSize], newName);
            (*returnSize)++;
        }
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    char** names = malloc(1000 * sizeof(char*));
    int namesSize = 0;
    
    char* token = strtok(line, "[]\",\n");
    while (token != NULL) {
        if (strlen(token) > 0 && strcmp(token, " ") != 0) {
            names[namesSize] = malloc(strlen(token) + 1);
            strcpy(names[namesSize], token);
            namesSize++;
        }
        token = strtok(NULL, "[]\",\n");
    }
    
    int returnSize;
    char** result = solution(names, namesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("\"%s\"", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through names with O(1) hash map operations

✓ Linear Growth

Space Complexity

O(n)

Hash map stores at most n unique base names plus result array

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map - Track Used Names — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler