Program for assigning usernames using Trie

0 0 13 minutes read

Suppose there is a queue of n users and your task is to assign a username to them. The system works in the following way. Every user has preferred login in the form of a string ‘s’ s consists only of small case letters and numbers. User name is assigned in the following order s, s0, s1, s2….s11…. means first you check s if s is available assign it if it is already occupied check for s0 if it is free assign it or if it is occupied check s1 and so on… if a username is assigned to one user it becomes occupied for other users after him in the queue.
Examples:

Input: names[] = {abc, bcd}
Output: user_names[] = {abc bcd}
Input: names[] = {abc, bcd, abc}
Output: user_names[] = {abc bcd abc0}
Input : names[] = {geek, geek0, geek1, geek}
Output : user_names[] = {geek geek0 geek1 geek2}
For first user geek is free so it is assigned to him similarly for the second and third user but for fourth user geek is not free so we will check geek0 but it is also not free then we will go for geek1 but it is also not free then we will check geek2 it is free so it is assigned to him.

We solve this problem using Trie. We do not use usual Trie which have 26 children but a Trie where nodes have 36 children 26 alphabets(a-z) and 10 numbers from (0-9). In addition to this each node of Trie will also have bool variable which will turn into true when a string ending at that node is inserted there will be a int variable as well lets call it add which will be initially -1 and suppose the string is geek and this int variable is equal to -1 then it means that we will directly return geek as it is asked for the first time but suppose it is 12 then it means that string geek, geek0…..geek12 are already present in the Trie.
Steps
Step 1: Maintain a Trie as discussed above.
Step 2: For every given name, check if the string given by user is not in the Trie then return the same string else start from i=add+1 (add is discussed above) and start checking if we concatenate i with the input string is present in the Trie or not if it is not present then return it and set add=i as well as insert it into Trie as well else increment i
Suppose string is geek and i=5 check if geek5 is in Trie or not if it is not present return geek5 set add for geek = 5 insert geek5 in Trie else if it is not present follow same steps for geek6 until you find a string that is not present in the Trie.

CPP

// C++ program to assign usernames to users
#include <bits/stdc++.h>
using namespace std;
 
#define MAX_CHAR 26
 
struct additional {
 
    // is checks if the current node is
    // leaf node or not
    bool is;
 
    // add counts number of concatenations
    // of string are present in Trie
    int add;
};
 
// represents Trie node
struct Trie {
 
    // MAX_CHAR character children
    Trie* character[MAX_CHAR];
 
    // 10 numbers (from 0 to 9)
    Trie* number[10];
 
    // one additional struct children
    additional a;
};
 
// function to get new node
Trie* getnew()
{
    // initialising the Trie node
    Trie* node = new Trie;
    node->a.is = false;
    node->a.add = -1;
    for (int i = 0; i < MAX_CHAR; i++)
        node->character[i] = NULL;
    for (int i = 0; i < 10; i++)
        node->number[i] = NULL;
    return node;
}
 
// inserting a string into Trie
void insert(Trie*& head, string s)
{
    Trie* curr = head;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] - 'a' < 0) {
            if (curr->number[s[i] - '0'] == NULL) {
                curr->number[s[i] - '0'] = getnew();
            }
            curr = curr->number[s[i] - '0'];
        }
        else {
            if (curr->character[s[i] - 'a'] == NULL)
                curr->character[s[i] - 'a'] = getnew();
            curr = curr->character[s[i] - 'a'];
        }
    }
    curr->a.is = true;
}
 
// returns the structure additional
additional search(Trie* head, string s)
{
    additional x;
    x.is = false;
    x.add = -1;
 
    // if head is null directly return additional x
    if (head == NULL)
        return x;
    Trie* curr = head;
 
    // checking if string is present or not and
    // accordingly returning x
    for (int i = 0; i < s.size(); i++) {
        if (s[i] - 'a' < 0) {
            curr = curr->number[s[i] - '0'];
        }
        else
            curr = curr->character[s[i] - 'a'];
        if (curr == NULL)
            return x;
    }
    x.is = curr->a.is;
    x.add = curr->a.add;
    return x;
}
 
// special function to update add variable to z
void update(Trie* head, string s, int z)
{
    Trie* curr = head;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] - 'a' < 0)
            curr = curr->number[s[i] - '0'];
        else
            curr = curr->character[s[i] - 'a'];
    }
    curr->a.add = z;
}
 
void printUsernames(string username[], int n)
{
    // Initializing a Trie root
    Trie* head = getnew();
 
    // Assigning usernames one by one
    for (int i = 0; i < n; i++) {
        string s = username[i];
        additional x = search(head, s);
 
        // if string is not present directly return it
        if (x.is == false) {
            cout << s << endl;
            insert(head, s);
        }
 
        // to_string(x) converts integer x into string
        else if (x.is == true) {
 
            // start from x.add+1
            int y = x.add + 1;
            string x = s;
 
            // continuing searching the string
            // until a free username is found
            while (1 < 2) {
 
                // if free username is found
                if (search(head, x + to_string(y)).is == false) {
 
                    // print it insert it and update add
                    cout << x << y << endl;
                    insert(head, x + to_string(y));
                    update(head, s, y);
                    break;
                }
                // else increment y
                else if (search(head, x + to_string(y)).is == true)
                    y++;
            }
        }
    }
}
 
// driver function
int main()
{
    string name[] = { "geek", "geek0", "geek1", "geek" };
    int n = sizeof(name) / sizeof(name[0]);
    printUsernames(name, n);
    return 0;
}

Java

// Java program to assign usernames to users
import java.util.HashMap;
import java.util.Map;
 
class Additional {
    // is checks if the current node is
    // leaf node or not
    boolean is;
    // add counts number of concatenations
    // of string are present in Trie
    int add;
 
    public Additional() {
        this.is = false;
        this.add = -1;
    }
}
 
// represents Trie node
class Trie {
    // character children
    Map<Character, Trie> children;
    // one additional struct children
    Additional a;
 
    public Trie() {
        this.children = new HashMap<>();
        this.a = new Additional();
    }
}
 
public class Main {
 
    // function to get new node
    public static Trie getNewNode() {
        // initialising the Trie node
        return new Trie();
    }
     
    // inserting a string into Trie
    public static void insert(Trie root, String s) {
        Trie curr = root;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                if (!curr.children.containsKey(c)) {
                    curr.children.put(c, getNewNode());
                }
                curr = curr.children.get(c);
            } else {
                if (!curr.children.containsKey(c)) {
                    curr.children.put(c, getNewNode());
                }
                curr = curr.children.get(c);
            }
        }
        curr.a.is = true;
    }
 
    // returns the structure additional
    public static Additional search(Trie root, String s) {
        Additional x = new Additional();
         
        // if head is null directly return additional x
        if (root == null) {
            return x;
        }
        Trie curr = root;
         
        // checking if string is present or not and
        // accordingly returning x
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!curr.children.containsKey(c)) {
                return x;
            }
            curr = curr.children.get(c);
        }
        x.is = curr.a.is;
        x.add = curr.a.add;
        return x;
    }
 
    // special function to update add variable to z
    public static void update(Trie root, String s, int z) {
        Trie curr = root;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            curr = curr.children.get(c);
        }
        curr.a.add = z;
    }
 
    public static void printUsernames(String[] username, int n) {
         
        // Initializing a Trie root
        Trie root = getNewNode();
         
        // Assigning usernames one by one
        for (int i = 0; i < n; i++) {
            String s = username[i];
            Additional x = search(root, s);
            // if string is not present directly return it
            if (!x.is) {
                System.out.println(s);
                insert(root, s);
            }
            // to_string(x) converts integer x into string
            else {
                // start from x.add+1
                int y = x.add + 1;
                String xString = s;
                 
                // continuing searching the string
                // until a free username is found
                while (true) {
                     // if free username is found
                    if (!search(root, xString + y).is) {
                        // print it insert it and update add
                        System.out.println(xString + y);
                        insert(root, xString + y);
                        update(root, xString, y);
                        break;
                    }
                    // else increment y
                    y++;
                }
            }
        }
    }
     
    // driver function
public static void main(String[] args) {
    String[] name = { "geek", "geek0", "geek1", "geek" };
    int n = name.length;
    printUsernames(name, n);
}
}
 
// This code is contributed by Aman Kumar.

Python

# python program to assign usernames to users
 
MAX_CHAR = 26
 
class Additional:
    # is checks if the current node is
    # leaf node or not
    def __init__(self):
        self.is_set = False
        # add counts number of concatenations
        # of string are present in Trie
        self.add = -1
 
# represents Trie node
class Trie:
    def __init__(self):
        # MAX_CHAR character children
        self.character = [None] * MAX_CHAR
         
        # 10 numbers (from 0 to 9)
        self.number = [None] * 10
         
        # one additional struct children
        self.a = Additional()
 
# function to get new node
def get_new():
    # initialising the Trie node
    node = Trie()
    node.a.is_set = False
    node.a.add = -1
    return node
 
# inserting a string into Trie
def insert(head, s):
    curr = head
    for i in range(len(s)):
        if ord(s[i]) - ord('a') < 0:
            if curr.number[int(s[i])] is None:
                curr.number[int(s[i])] = get_new()
            curr = curr.number[int(s[i])]
        else:
            if curr.character[ord(s[i]) - ord('a')] is None:
                curr.character[ord(s[i]) - ord('a')] = get_new()
            curr = curr.character[ord(s[i]) - ord('a')]
    curr.a.is_set = True
 
# returns the structure additional
def search(head, s):
    x = Additional()
    x.is_set = False
    x.add = -1
     
    # if head is null directly return additional x
    if head is None:
        return x
 
    curr = head
     
    # checking if string is present or not and
    # accordingly returning x
    for i in range(len(s)):
        if ord(s[i]) - ord('a') < 0:
            curr = curr.number[int(s[i])]
        else:
            curr = curr.character[ord(s[i]) - ord('a')]
        if curr is None:
            return x
 
    x.is_set = curr.a.is_set
    x.add = curr.a.add
    return x
 
# special function to update add variable to z
def update(head, s, z):
    curr = head
    for i in range(len(s)):
        if ord(s[i]) - ord('a') < 0:
            curr = curr.number[int(s[i])]
        else:
            curr = curr.character[ord(s[i]) - ord('a')]
    curr.a.add = z
 
def print_usernames(username):
    # Initializing a Trie root
    head = get_new()
     
    # Assigning usernames one by one
    for s in username:
        x = search(head, s)
         
        # if string is not present directly return it
        if not x.is_set:
            print(s)
            insert(head, s)
         
        # to_string(x) converts integer x into string
        elif x.is_set:
             
            # start from x.add+1
            y = x.add + 1
            t = s
             
            # continuing searching the string
            # until a free username is found
            while True:
                 
                # if free username is found
                if not search(head, t + str(y)).is_set:
                    # print it insert it and update add
                    print(t + str(y))
                    insert(head, t + str(y))
                    update(head, s, y)
                    break
                 
                # else increment y
                elif search(head, t + str(y)).is_set:
                    y += 1
 
# driver function
if __name__ == '__main__':
    name = ["geek", "geek0", "geek1", "geek"]
    print_usernames(name)
 
 
# this code is contributed by bhardwajji

C#

// C# program to assign usernames to users
using System;
using System.Collections.Generic;
 
public class Additional {
    // is checks if the current node is
    // leaf node or not
    public bool IS;
    // add counts number of concatenations
    // of string are present in Trie
    public int add;
 
    public Additional() {
        IS = false;
        add = -1;
    }
}
 
// represents Trie node
public class Trie {
    // character children
    public Dictionary<char, Trie> children;
    // one additional struct children
    public Additional a;
 
    public Trie() {
        children = new Dictionary<char, Trie>();
        a = new Additional();
    }
}
 
public class MainClass {
    // function to get new node
    public static Trie GetNewNode() {
        // initialising the Trie node
        return new Trie();
    }
 
    // inserting a string into Trie
    public static void Insert(Trie root, string s) {
        Trie curr = root;
        for (int i = 0; i < s.Length; i++) {
            char c = s[i];
            if (Char.IsDigit(c)) {
                if (!curr.children.ContainsKey(c)) {
                    curr.children = GetNewNode();
                }
                curr = curr.children;
            } else {
                if (!curr.children.ContainsKey(c)) {
                    curr.children = GetNewNode();
                }
                curr = curr.children;
            }
        }
        curr.a.IS = true;
    }
 
    // returns the structure additional
    public static Additional Search(Trie root, string s) {
        Additional x = new Additional();
        // if head is null directly return additional x
        if (root == null) {
            return x;
        }
        Trie curr = root;
        // checking if string is present or not and
        // accordingly returning x
        for (int i = 0; i < s.Length; i++) {
            char c = s[i];
            if (!curr.children.ContainsKey(c)) {
                return x;
            }
            curr = curr.children;
        }
        x.IS = curr.a.IS;
        x.add = curr.a.add;
        return x;
    }
 
    // special function to update add variable to z
    public static void Update(Trie root, string s, int z) {
        Trie curr = root;
        for (int i = 0; i < s.Length; i++) {
            char c = s[i];
            curr = curr.children;
        }
        curr.a.add = z;
    }
 
    public static void PrintUsernames(string[] username, int n) {
        // Initializing a Trie root
        Trie root = GetNewNode();
         
        // Assigning usernames one by one
        for (int i = 0; i < n; i++) {
            string s = username[i];
            Additional x = Search(root, s);
            // if string is not present directly return it
            if (!x.IS) {
                Console.WriteLine(s);
                Insert(root, s);
            } 
            // to_string(x) converts integer x into string
            else {
                // start from x.add+1
                int y = x.add + 1;
                string xString = s;
                 
                // continuing searching the string
                // until a free username is found
                while (true) {
                    // if free username is found
                    if (!Search(root, xString + y).IS) {
                        // print it insert it and update add
                        Console.WriteLine(xString + y);
                        Insert(root, xString + y);
                        Update(root, xString, y);
                        break;
                    }
                    // else increment y
                    y++;
                }
            }
        }
    }
    // driver function
    public static void Main() {
        string[] name = { "geek", "geek0", "geek1", "geek" };
        int n = name.Length;
        PrintUsernames(name, n);
    }
}
 
// This code is contributed by Vaibhav

Javascript

const MAX_CHAR = 26;
 
class Additional {
  constructor() {
    this.is_set = false;
    this.add = -1;
  }
}
 
class Trie {
  constructor() {
    this.character = Array(MAX_CHAR).fill(null);
    this.number = Array(10).fill(null);
    this.a = new Additional();
  }
}
 
function get_new() {
  const node = new Trie();
  node.a.is_set = false;
  node.a.add = -1;
  return node;
}
 
function insert(head, s) {
  let curr = head;
  for (let i = 0; i < s.length; i++) {
    if (s.charCodeAt(i) - 'a'.charCodeAt(0) < 0) {
      if (curr.number[parseInt(s[i])] === null) {
        curr.number[parseInt(s[i])] = get_new();
      }
      curr = curr.number[parseInt(s[i])];
    } else {
      if (curr.character[s.charCodeAt(i) - 'a'.charCodeAt(0)] === null) {
        curr.character[s.charCodeAt(i) - 'a'.charCodeAt(0)] = get_new();
      }
      curr = curr.character[s.charCodeAt(i) - 'a'.charCodeAt(0)];
    }
  }
  curr.a.is_set = true;
}
 
function search(head, s) {
  const x = new Additional();
  x.is_set = false;
  x.add = -1;
 
  if (head === null) {
    return x;
  }
 
  let curr = head;
 
  for (let i = 0; i < s.length; i++) {
    if (s.charCodeAt(i) - 'a'.charCodeAt(0) < 0) {
      curr = curr.number[parseInt(s[i])];
    } else {
      curr = curr.character[s.charCodeAt(i) - 'a'.charCodeAt(0)];
    }
    if (curr === null) {
      return x;
    }
  }
 
  x.is_set = curr.a.is_set;
  x.add = curr.a.add;
  return x;
}
 
function update(head, s, z) {
  let curr = head;
  for (let i = 0; i < s.length; i++) {
    if (s.charCodeAt(i) - 'a'.charCodeAt(0) < 0) {
      curr = curr.number[parseInt(s[i])];
    } else {
      curr = curr.character[s.charCodeAt(i) - 'a'.charCodeAt(0)];
    }
  }
  curr.a.add = z;
}
 
function print_usernames(username) {
  const head = get_new();
  for (let s of username) {
    const x = search(head, s);
    if (!x.is_set) {
      console.log(s);
      insert(head, s);
    } else if (x.is_set) {
      let y = x.add + 1;
      let t = s;
      while (true) {
        if (!search(head, t + y.toString()).is_set) {
          console.log(t + y.toString());
          insert(head, t + y.toString());
          update(head, s, y);
          break;
        } else if (search(head, t + y.toString()).is_set) {
          y += 1;
        }
      }
    }
  }
}
 
const name = ["geek", "geek0", "geek1", "geek"];
print_usernames(name);

Output

geek
geek0
geek1
geek2

Approach: Using a HashSet

Below is the code implementation of the above approach:

C++

// C++ program of the above approach
 
#include <iostream>
#include <unordered_set>
#include <vector>
 
using namespace std;
 
vector<string> assignUsernames(const vector<string>& names)
{
    // HashSet to store occupied usernames
    unordered_set<string> occupiedUsernames;
    // Vector to store assigned usernames
    vector<string> userNames;
 
    // Iterate through each name in the input vector
    for (const string& name : names) {
        string assignedName = name;
        int count = 0;
 
        while (occupiedUsernames.count(assignedName) > 0) {
            // Append suffix to assignedName
            assignedName = name + to_string(count);
            count++;
        }
 
        userNames.push_back(assignedName);
        occupiedUsernames.insert(assignedName);
    }
    // Return the vector of assigned usernames
    return userNames;
}
 
// Driver Code
int main()
{
    vector<string> names = { "abc", "bcd", "abc" };
    vector<string> assignedUsernames
        = assignUsernames(names);
 
    for (const string& username : assignedUsernames) {
        cout << username << " ";
    }
 
    return 0;
}

Java

import java.util.HashSet;
import java.util.Vector;
 
public class Main {
 
    // Function to assign usernames to a list of names
    public static Vector<String> assignUsernames(Vector<String> names) {
        // HashSet to store occupied usernames
        HashSet<String> occupiedUsernames = new HashSet<>();
        // Vector to store assigned usernames
        Vector<String> userNames = new Vector<>();
 
        // Iterate through each name in the input vector
        for (String name : names) {
            String assignedName = name;
            int count = 0;
 
            while (occupiedUsernames.contains(assignedName)) {
                // Append suffix to assignedName
                assignedName = name + count;
                count++;
            }
 
            userNames.add(assignedName);
            occupiedUsernames.add(assignedName);
        }
        // Return the vector of assigned usernames
        return userNames;
    }
 
    public static void main(String[] args) {
        Vector<String> names = new Vector<>();
        names.add("abc");
        names.add("bcd");
        names.add("abc");
        Vector<String> assignedUsernames = assignUsernames(names);
 
        for (String username : assignedUsernames) {
            System.out.print(username + " ");
        }
    }
}

C#

// C# program of the above approach
using System;
using System.Collections.Generic;
 
class Program
{
    static List<string> AssignUsernames(List<string> names)
    {
        // HashSet to store occupied usernames
        HashSet<string> occupiedUsernames = new HashSet<string>();
        // List to store assigned usernames
        List<string> userNames = new List<string>();
 
        // Iterate through each name in the input list
        foreach (string name in names)
        {
            string assignedName = name;
            int count = 0;
 
            while (occupiedUsernames.Contains(assignedName))
            {
                // Append suffix to assignedName
                assignedName = name + count.ToString();
                count++;
            }
 
            userNames.Add(assignedName);
            occupiedUsernames.Add(assignedName);
        }
        // Return the list of assigned usernames
        return userNames;
    }
 
    // Driver Code
    static void Main()
    {
        List<string> names = new List<string> { "abc", "bcd", "abc" };
        List<string> assignedUsernames = AssignUsernames(names);
 
        foreach (string username in assignedUsernames)
        {
            Console.Write(username + " ");
        }
    }
}

Output

abc bcd abc0

Time Complexity: O(nm), where n is the number of names in the input vector and m is the length of the longest name.
Auxiliary Space: O(nm)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!