We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Making File Names Unique

Number: 1611

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an array of strings representing folder names to be created sequentially, the task is to assign a unique name to each folder. When a folder name conflicts with a previously used name, the system appends a suffix in the form of (k), where k is the smallest positive integer that makes the folder name unique.

Key Insights

  • Use a hash table (dictionary/map) to keep track of existing folder names and the next suffix number for duplicates.
  • When encountering a name, if it is unique, add it directly to the answer and record it in the hash table.
  • If the name has already been used, find the smallest integer k for which name(k) is not in the hash table, update the dictionary accordingly, and use that name.
  • Checking and updating the dictionary ensures constant time operations on average.

Space and Time Complexity

Time Complexity: O(n) on average, where n is the number of folder names, since each name is processed in constant time with average O(1) hash table operations. Space Complexity: O(n) for storing the folder names and their counters in the hash table.

Solution

We solve the problem by iterating over the given list of names:

  1. For each folder name:
    • If the name has not been seen before (not in the hash table), add it to the result and mark it as seen.
    • If the name exists, determine the smallest integer k such that the new name in the form of "name(k)" is unique. We do this by checking from the previously stored counter value.
    • Update the hash table for both the original name and the new name.
  2. This approach ensures that for every duplicate the smallest possible valid suffix is used.

Data Structures: A hash table (dictionary/map) to store each name and the next suffix number. Algorithmic Approach: Iterative processing with constant-time checks and updates using the hash table.

Code Solutions

# Python implementation with detailed comments

def getFolderNames(names):
    # Dictionary to store the count for each base folder name.
    name_count = {}
    # List to hold the final folder names.
    result = []
    
    # Iterate through each folder name in the input list.
    for name in names:
        # If the folder name is not already used, use it as is.
        if name not in name_count:
            result.append(name)
            # Mark the name as used and initialize its counter.
            name_count[name] = 0
        else:
            # Get the next available suffix starting from the current count plus one.
            k = name_count[name] + 1
            new_name = f"{name}({k})"
            # Continue to increase k until a unique name is found.
            while new_name in name_count:
                k += 1
                new_name = f"{name}({k})"
            # Update the base name counter to the last tried k.
            name_count[name] = k
            # Mark the newly created name as used.
            name_count[new_name] = 0
            result.append(new_name)
    return result

# Example usage:
# names = ["gta", "gta(1)", "gta", "avalon"]
# print(getFolderNames(names))
← Back to All Questions