Given an array of strings names of size n. You will create n folders in your file system such that, at the ith 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 which is 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 ith folder when you create it.
 
Example 1:
Input: names = ["pes","fifa","gta","pes(2019)"]
Output: ["pes","fifa","gta","pes(2019)"]
Explanation: Let's see how the file system creates folder names:
"pes" --> not assigned before, remains "pes"
"fifa" --> not assigned before, remains "fifa"
"gta" --> not assigned before, remains "gta"
"pes(2019)" --> not assigned before, remains "pes(2019)"

Example 2:
Input: names = ["gta","gta(1)","gta","avalon"]
Output: ["gta","gta(1)","gta(2)","avalon"]
Explanation: Let's see how the file system creates folder names:
"gta" --> not assigned before, remains "gta"
"gta(1)" --> not assigned before, remains "gta(1)"
"gta" --> the name is reserved, system adds (k), since "gta(1)" is also reserved, systems put k = 2. it becomes "gta(2)"
"avalon" --> not assigned before, remains "avalon"

Example 3:
Input: names = ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece"]
Output: ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece(4)"]
Explanation: When the last folder is created, the smallest positive valid k is 4, and it becomes "onepiece(4)".

Example 4:
Input: names = ["wano","wano","wano","wano"]
Output: ["wano","wano(1)","wano(2)","wano(3)"]
Explanation: Just increase the value of k each time you create folder "wano".

Example 5:
Input: names = ["kaido","kaido(1)","kaido","kaido(1)"]
Output: ["kaido","kaido(1)","kaido(2)","kaido(1)(1)"]
Explanation: Please note that system adds the suffix (k) to current name even it contained the same suffix before.

 
Constraints:

1 <= names.length <= 5 * 10^4
1 <= names[i].length <= 20
names[i] consists of lower case English letters, digits and/or round brackets.

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: class Solution:
    def getFolderNames(self, names: List[str]) -> List[str]:
        

Solutions:
class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		(used, hashmap) = (set(), defaultdict(int))
		result = []
		for name in names:
			k = hashmap[name]
			current = name
			while current in used:
				k += 1
				current = '%s(%d)' % (name, k)
			hashmap[name] = k
			result.append(current)
			used.add(current)
		return result


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		seen_set = set()
		new_names = []
		for name in names:
			new_name = name
			if new_name in seen_set:
				i = 1
				while new_name in seen_set:
					new_name = f'{name}({i})'
					i += 1
			new_names.append(new_name)
			seen_set.add(new_name)
		return new_names


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		strs = set()
		new_strs = []
		for name in names:
			if name not in strs:
				strs.add(name)
				new_strs.append(name)
			else:
				i = 1
				while True:
					new_str = f'{name}({i})'
					if new_str not in strs:
						strs.add(new_str)
						new_strs.append(new_str)
						break
					i += 1
		return new_strs


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		hashmap = {}
		res = []
		for name in names:
			if name not in hashmap:
				hashmap[name] = True
				res.append(name)
			else:
				i = 1
				_name = f'{name}({i})'
				while _name in hashmap:
					i += 1
					_name = f'{name}({i})'
				hashmap[_name] = True
				res.append(_name)
		return res


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		created_fld = set()
		result_set = []
		for name in names:
			if name not in created_fld:
				created_fld.add(name)
				result_set.append(name)
			else:
				j = 1
				new_name = f'{name}({j})'
				while new_name in created_fld:
					j += 1
					new_name = f'{name}({j})'
				created_fld.add(new_name)
				result_set.append(new_name)
		return result_set


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		if len(names) <= 1:
			return names
		used = set()
		newNames = []
		for name in names:
			if name in used:
				k = 1
				numName = f'{name}({k})'
				while numName in used:
					k += 1
					numName = f'{name}({k})'
				used.add(numName)
				newNames.append(numName)
			else:
				used.add(name)
				newNames.append(name)
		return newNames


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		a = set()
		b = []
		for i in names:
			if i in a:
				k = 1
				s = f'{i}({k})'
				while s in a:
					k += 1
					s = f'{i}({k})'
				a.add(s)
				b.append(s)
			else:
				a.add(i)
				b.append(i)
		return b


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		if len(names) <= 1:
			return names
		used = set()
		for (p, i) in enumerate(names):
			if i not in used:
				used.add(i)
				names[p] = i
			else:
				oldi = i
				k = 0
				while i in used:
					k += 1
					i = f'{oldi}({k})'
				used.add(i)
				names[p] = i
		return names


class Solution:

	def getFolderNames1(self, names: List[str]) -> List[str]:
		memo = dict()
		seen = set()
		sol = []
		for s in names:
			if s and s[-1] == ')':
				if s in memo:
					memo[s] += 1
				else:
					memo[s] = 0
				base = s
			else:
				base = s
				memo[base] = 0
			k = memo[base]
			while True:
				if k == 0:
					target = base
				else:
					target = base + '(' + str(k) + ')'
				if target in seen:
					k += 1
				else:
					sol.append(target)
					seen.add(target)
					break
			memo[base] = k
		return sol

	def getFolderNames(self, names: List[str]) -> List[str]:
		seen = set()
		sol = []
		for s in names:
			if s in seen:
				k = 1
				target = f'{s}({k})'
				while target in seen:
					k += 1
					target = f'{s}({k})'
				sol.append(target)
				seen.add(target)
			else:
				sol.append(s)
				seen.add(s)
		return sol


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		version = {}
		ans = []
		for k in names:
			if k not in version:
				ans.append(k)
				version[k] = 1
			else:
				res = k + '(' + str(version[k]) + ')'
				while res in version:
					version[k] += 1
					res = k + '(' + str(version[k]) + ')'
				ans.append(res)
				version[res] = 1
		return ans


def get_names(names):
	next_index = {}
	ans = []
	for name in names:
		if name not in next_index:
			next_index[name] = 1
			ans.append(name)
		else:
			index = next_index[name]
			while f'{name}({index})' in next_index:
				index += 1
			next_index[name] = index
			new_name = f'{name}({index})'
			assert new_name not in next_index
			next_index[new_name] = 1
			ans.append(new_name)
	return ans

class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		return get_names(names)


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		ans = []
		folders = {}
		for n in names:
			if n not in folders:
				folders[n] = 1
				ans.append(n)
			else:
				i = folders[n]
				while f'{n}({i})' in folders:
					i += 1
				ans.append(f'{n}({i})')
				folders[f'{n}({i})'] = 1
				folders[n] = i + 1
		return ans


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		h = dict()
		ans = []
		for i in names:
			if i not in h:
				h[i] = 1
				ans.append(i)
			else:
				ct = h[i]
				tmp = i + '(' + str(ct) + ')'
				while tmp in h:
					ct += 1
					tmp = i + '(' + str(ct) + ')'
				h[tmp] = 1
				ans.append(tmp)
				h[i] = ct
		return ans


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		d = {}
		res = []
		for name in names:
			if name not in d:
				d[name] = 1
				new_name = name
			else:
				k = d[name]
				while name + '(' + str(k) + ')' in d:
					k += 1
				new_name = name + '(' + str(k) + ')'
				d[name] = k
				d[new_name] = 1
			res.append(new_name)
		return res


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		memo = defaultdict(int)
		res = []
		for n in names:
			if memo[n] > 0:
				while n + '(' + str(memo[n]) + ')' in memo:
					memo[n] += 1
				name = n + '(' + str(memo[n]) + ')'
				res.append(name)
				memo[name] += 1
			else:
				res.append(n)
			memo[n] += 1
		return res


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		(ans, suffixNum) = ([], Counter())
		for name in names:
			if name in suffixNum:
				while name + '(' + str(suffixNum[name]) + ')' in suffixNum:
					suffixNum[name] += 1
				ans.append(name + '(' + str(suffixNum[name]) + ')')
			else:
				ans.append(name)
			suffixNum[ans[-1]] += 1
		return ans


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		d = {}
		ans = []
		for i in names:
			if i not in list(d.keys()):
				ans.append(i)
				d[i] = [1, set()]
				continue
			(curno, sets) = d[i]
			while curno in sets or i + '(' + str(curno) + ')' in list(d.keys()):
				curno += 1
			ans.append(i + '(' + str(curno) + ')')
			d[i + '(' + str(curno) + ')'] = [1, set()]
			d[i][0] = curno + 1
		return ans


class Solution:

	def getFolderNames(self, names):
		res = []
		allname = collections.Counter()
		for name in names:
			if name in allname:
				while f'{name}({allname[name]})' in allname:
					allname[name] += 1
				res.append(f'{name}({allname[name]})')
				allname[f'{name}({allname[name]})'] = 1
			else:
				allname[name] = 1
				res.append(name)
		return res


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		mem = collections.defaultdict(int)
		res = []
		for n in names:
			if mem[n] > 0:
				while n + '(' + str(mem[n]) + ')' in mem:
					mem[n] += 1
				res.append(n + '(' + str(mem[n]) + ')')
				mem[n + '(' + str(mem[n]) + ')'] += 1
			else:
				res.append(n)
			mem[n] += 1
		return res


class Solution:

	def getFolderNames(self, lis: List[str]) -> List[str]:
		s = set()
		ans = []
		d = {}
		for i in lis:
			if i in s:
				k = d[i]
				while 1 > 0:
					tmp = '%s(%d)' % (i, k)
					if tmp in s:
						k += 1
					else:
						break
				d[i] = k
				d['%s(%d)' % (i, k)] = 1
				s.add('%s(%d)' % (i, k))
				ans.append('%s(%d)' % (i, k))
			else:
				d[i] = 1
				s.add(i)
				ans.append(i)
		return ans


from typing import List

class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		exists = {}
		res = []
		for name in names:
			if name not in exists:
				res.append(name)
				exists[name] = 1
			else:
				newName = '{}({})'.format(name, exists[name])
				exists[name] += 1
				while newName in exists:
					newName = '{}({})'.format(name, exists[name])
					exists[name] += 1
				exists[newName] = 1
				res.append(newName)
		return res
s = Solution()


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		exists = set()
		last = collections.defaultdict(int)
		result = []
		for name in names:
			k = last[name]
			modified = name
			while modified in exists:
				k += 1
				modified = f'{name}({k})'
			last[name] = k
			result.append(modified)
			exists.add(modified)
		return result


from collections import defaultdict

class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		memo = defaultdict(int)
		res = []
		for name in names:
			if memo[name] > 0:
				while f'{name}({memo[name]})' in memo.keys():
					memo[name] += 1
				res.append(f'{name}({memo[name]})')
				memo[f'{name}({memo[name]})'] += 1
			else:
				res.append(name)
			memo[name] += 1
		return res


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		existing = {}
		output = []
		for name in names:
			if name not in existing.keys():
				existing[name] = 1
				output.append(name)
			else:
				k = existing[name]
				while True:
					new_name = '{}({})'.format(name, k)
					if new_name not in existing:
						existing[new_name] = 1
						existing[name] = k + 1
						output.append(new_name)
						break
					k += 1
		return output


import re
from collections import defaultdict

class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		mapping = defaultdict(lambda : -1)
		ans = []
		for name in names:
			if name in mapping:
				count = mapping[name] + 1
				fname = f'{name}({count})'
				while fname in mapping:
					count += 1
					fname = f'{name}({count})'
				mapping[name] = count
			else:
				fname = name
			mapping[fname] += 1
			ans.append(fname)
		return ans


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		map = Counter()
		ans = []
		for s in names:
			if map[s] == 0:
				ans.append(s)
				map[s] += 1
			else:
				while map[s + '(' + str(map[s]) + ')'] != 0:
					map[s] += 1
				map[s + '(' + str(map[s]) + ')'] += 1
				ans.append(s + '(' + str(map[s]) + ')')
		return ans


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		ans = []
		used = collections.defaultdict(set)
		m = collections.defaultdict(int)
		for raw in names:
			added = False
			res = re.search(f'\\([1-9][0-9]*\\)$', raw)
			if res:
				n = int(res.group(0)[1:-1])
				name = raw[:res.start(0)]
				if n not in used[name]:
					added = True
					used[name].add(n)
					while m[name] in used[name]:
						m[name] += 1
					ans.append(f'{name}({n})')
			name = raw
			while m[name] in used[name]:
				m[name] += 1
			n = m[name]
			used[name].add(n)
			if not added:
				ans.append(f'{name}({n})' if n else name)
			if n:
				name = f'{name}({n})'
				while m[name] in used[name]:
					m[name] += 1
				n = m[name]
				used[name].add(n)
		return ans


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		prefix_counts = dict()
		ret = []
		for name in names:
			if name not in prefix_counts:
				ret.append(name)
				prefix_counts[name] = 0
			else:
				temp_count = prefix_counts[name] + 1
				while f'{name}({temp_count})' in prefix_counts:
					temp_count += 1
				prefix_counts[name] = temp_count
				new_name = f'{name}({prefix_counts[name]})'
				prefix_counts[new_name] = 0
				ret.append(new_name)
		return list(ret)


from collections import defaultdict

class Solution:

	def add_suffix(self, name, suffix):
		if suffix == 0:
			return name
		name = name + '(' + str(suffix) + ')'
		return name

	def get_prefix_suff_num(self, name):
		if name.rfind('(') != -1:
			prefix_end = name.rfind('(') - 1
			suff = 0
			i = prefix_end + 2
			while ord(name[i]) >= ord('0') and ord(name[i]) <= ord('9'):
				suff = suff * 10 + ord(name[i]) - ord('0')
				i += 1
		else:
			prefix_end = len(name) - 1
			suff = 0
		return (name[:prefix_end + 1], suff)

	def get_next_suffix(self, suff, name_suffixes, next_map, name):
		while suff in name_suffixes:
			suff += 1
		next_map[name] = suff

	def getFolderNames(self, names: List[str]) -> List[str]:
		next_map = defaultdict(int)
		suffix_map = defaultdict(set)
		ans = []
		for name in names:
			suffix = next_map[name]
			suffix_map[name].add(suffix)
			new = self.add_suffix(name, suffix)
			suffix_map[new].add(0)
			(prefix, suff_number) = self.get_prefix_suff_num(name)
			if len(prefix) < len(name) and suff_number != 0 or len(prefix) == len(name):
				suffix_map[prefix].add(suff_number)
				self.get_next_suffix(next_map[prefix], suffix_map[prefix], next_map, prefix)
			self.get_next_suffix(suffix, suffix_map[name], next_map, name)
			self.get_next_suffix(next_map[new], suffix_map[new], next_map, new)
			ans.append(new)
		return ans


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		ht = {}
		res = OrderedDict()
		for name in names:
			if name not in ht:
				ht[name] = 1
			if name not in res:
				res[name] = True
				continue
			key = name + '(' + str(ht[name]) + ')'
			while key in res:
				ht[name] += 1
				key = name + '(' + str(ht[name]) + ')'
			res[key] = True
		return res


from collections import Counter

class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		(cnt, ans) = (Counter(), [])
		for name in names:
			if name not in cnt:
				ans.append(name)
				cnt[name] += 1
			else:
				while name + '(' + str(cnt[name]) + ')' in cnt:
					cnt[name] += 1
				ans.append(name + '(' + str(cnt[name]) + ')')
				cnt[name + '(' + str(cnt[name]) + ')'] += 1
		return ans


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		from collections import defaultdict
		seen = set()
		hashmap = defaultdict(int)
		ans = []
		for name in names:
			k = hashmap[name]
			current = name
			while current in seen:
				k += 1
				current = f'{name}({k})'
			hashmap[name] = k
			seen.add(current)
			ans.append(current)
		return ans


from collections import defaultdict

class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		d = defaultdict(int)
		for (idx, i) in enumerate(names):
			suffix = i
			orig = False
			if suffix not in d:
				orig = True
			while suffix in d:
				suffix = i + '(' + str(d[i]) + ')'
				d[i] += 1
			names[idx] = suffix
			if orig:
				d[i] += 1
			else:
				d[suffix] += 1
		return names


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		d = dict()
		for name in names:
			d[name] = d.get(name, 0) + 1
			if d[name] > 1:
				i = d[name] - 1
				temp = name + '(' + str(i) + ')'
				while temp in d:
					i += 1
					temp = name + '(' + str(i) + ')'
				d[name] = i + 1
				d[temp] = 1
		return d.keys()


class Information:

	def __init__(self):
		self.next = 0
		self.used = set()

class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		(result, occupied) = ([], collections.defaultdict(Information))
		for name in names:
			if name in occupied:
				info = occupied[name]
				while info.next in info.used:
					info.used.remove(info.next)
					info.next += 1
				final_name = name if info.next == 0 else '{}({})'.format(name, info.next)
			else:
				final_name = name
			if final_name[-1] == ')':
				scan = len(final_name) - 2
				while scan >= 0 and final_name[scan].isdigit():
					scan -= 1
				if scan >= 0 and final_name[scan] == '(' and (int(final_name[scan + 1:-1]) > 0):
					occupied[final_name[:scan]].used.add(int(final_name[scan + 1:-1]))
			occupied[name].next += 1
			if name != final_name:
				occupied[final_name].next += 1
			result.append(final_name)
		return result


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		used = defaultdict(int)
		ans = []
		for name in names:
			if name not in used:
				ans.append(name)
				used[name] += 1
			else:
				num = used[name]
				tmp = f'{name}({used[name]})'
				while tmp in used:
					num += 1
					tmp = f'{name}({num})'
				ans.append(tmp)
				if tmp not in used:
					used[tmp] = 1
				used[name] = max(used[name] + 1, num)
		return ans


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		rec = []
		res = {}
		for file in names:
			if file in res.keys():
				n = res[file]
				tmp = file + '(' + str(n) + ')'
				while tmp in res.keys():
					n += 1
					tmp = file + '(' + str(n) + ')'
				rec.append(tmp)
				res[tmp] = 1
				res[file] += 1
			else:
				res[file] = 1
				rec.append(file)
		return rec


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		hashmap = {}
		seen = set()
		ans = []
		for name in names:
			k = hashmap.setdefault(name, 0)
			current = name
			while current in seen:
				k += 1
				current = f'{name}({k})'
			hashmap[name] = k
			seen.add(current)
			ans.append(current)
		return ans


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		(_map, ans) = (defaultdict(int), [])
		for name in names:
			if _map[name] > 0:
				print(name)
				while name + '(' + str(_map[name]) + ')' in _map:
					_map[name] += 1
				ans.append(name + '(' + str(_map[name]) + ')')
				_map[name + '(' + str(_map[name]) + ')'] += 1
				_map[name] += 1
			else:
				_map[name] += 1
				ans.append(name)
		return ans


class Solution:
	from collections import defaultdict

	def getFolderNames(self, lis: List[str]) -> List[str]:
		s = set()
		ans = []
		d = defaultdict(int)
		for i in lis:
			k = d[i]
			cur = i
			while cur in s:
				k += 1
				cur = '%s(%d)' % (i, k)
			d[i] = k
			s.add(cur)
			ans.append(cur)
		return ans


class Solution:

	def getFolderNames(self, names: List[str]) -> List[str]:
		m = set()
		m2 = dict()
		f = []
		for x in names:
			if x not in m:
				m.add(x)
				f.append(x)
				m2[x] = 1
			elif x in m2:
				while x + '(' + str(m2[x]) + ')' in m:
					m2[x] += 1
				m.add(x + '(' + str(m2[x]) + ')')
				f.append(x + '(' + str(m2[x]) + ')')
			else:
				m2[x] = 1
				while x + '(' + str(m2[x]) + ')' in m:
					m2[x] += 1
				m.add(x + '(' + str(m2[x]) + ')')
				f.append(x + '(' + str(m2[x]) + ')')
		return f