Python – Concatenate Dynamic Frequency

Given List of elements, perform concatenation with frequency dynamically, i.e each element is concatenated with its frequency till its index.

Input : test_list = [‘z’, ‘z’, ‘e’, ‘f’, ‘f’] 
Output : [‘1z’, ‘2z’, ‘1e’, ‘1f’, ‘2f’] 
Explanation : As occurrence increase, concat number is increased. 

Input : test_list = [‘g’, ‘f’, ‘g’] 
Output : [‘1g’, ‘1f’, ‘2g’] 
Explanation : As occurrence increase, concat number is increased.

Method 1 : Using defaultdict() + “+” operator + str()

In this, the dynamic frequency computation is done using defaultdict() and str() is used to convert elements to string for valid concatenation using “+” operator.

The original list is : ['z', 'z', 'e', 'f', 'f', 'e', 'f', 'z', 'c']
Dynamic Frequency list : ['1z', '2z', '1e', '1f', '2f', '2e', '3f', '3z', '1c']

Time Complexity: O(n)
Auxiliary Space: O(n)

Method 2: Using slicing and count() method

The original list is : ['z', 'z', 'e', 'f', 'f', 'e', 'f', 'z', 'c']
Dynamic Frequency list : ['1z', '2z', '1e', '1f', '2f', '2e', '3f', '3z', '1c']

Time Complexity: O(n)
Auxiliary Space: O(n)

Method 3:  Using operator.countOf() method

The original list is : ['z', 'z', 'e', 'f', 'f', 'e', 'f', 'z', 'c']
Dynamic Frequency list : ['1z', '2z', '1e', '1f', '2f', '2e', '3f', '3z', '1c']

Time Complexity: O(N)
Auxiliary Space : O(N)

Method 4: Using dictionary comprehension + f-string

This approach also uses a dictionary to keep track of the frequency of each element and concatenates the frequency with the element using f-strings. Then, it creates a list of the concatenated strings using dictionary comprehension.

Follow the below steps to implement the above idea:

1. Initialize the input list test_list with the given values.
2. Create an empty dictionary memo to keep track of the frequency of each element.
3. Iterate over each element ele in the test_list.
4. Check if the element ele already exists in the memo dictionary.
5. If the element ele exists in the memo dictionary, increment its frequency count by 1.
6. If the element ele does not exist in the memo dictionary, set its frequency count to 1.
7. Concatenate the frequency of the element ele with the element ele using f-strings and append it to the res list.
8. Return the final concatenated list res using dictionary comprehension.
9. Print the result.

Below is the implementation of the above approach:

The original list is : ['z', 'z', 'e', 'f', 'f', 'e', 'f', 'z', 'c']
Dynamic Frequency list : ['3z', '3z', '2e', '3f', '3f', '2e', '3f', '3z', '1c']

Time complexity: O(n)
Auxiliary space: O(n)

Method 5: Using Counter() from collections module

Approach:

1. Import the Counter() function from the collections module.
2. Pass the original list as an argument to the Counter() function to create a dictionary with the frequency of each element.
3. Use a list comprehension to iterate over the original list and concatenate the frequency with each element.
4. Store the concatenated strings in a new list.
5. Print the new list.

Below is the implementation of the above approach:

The original list is : ['z', 'z', 'e', 'f', 'f', 'e', 'f', 'z', 'c']
Dynamic Frequency list : ['3z', '3z', '2e', '3f', '3f', '2e', '3f', '3z', '1c']

Time complexity: O(n + k log k), where n is the length of the input list and k is the number of unique elements in the list.
Auxiliary space: O(n + k), where n is the length of the input list and k is the number of unique elements in the list.

Method 6: Using a loop and list comprehension

1. We first initialize the input list test_list with some values.
2. We print the original list using print().
3. We use a loop and list comprehension to generate the dynamic frequency list.
4. We iterate over the indices of the elements in test_list using enumerate().
5. For each element ele in test_list, we slice the list up to that index using test_list[:i+1].
6. We count the frequency of the element in the sliced list using the count() method.
7. We concatenate the frequency with the element using the + operator and append it to the res list.
8. Finally, we print the dynamic frequency list using print().

Example:

The original list is : ['z', 'z', 'e', 'f', 'f', 'e', 'f', 'z', 'c']
Dynamic Frequency list : ['1z', '2z', '1e', '1f', '2f', '2e', '3f', '3z', '1c']

Time complexity: O(n^2) due to the nested loops used in the count() method, where n is the length of the input list. 
Auxiliary space: O(n) because we are using an additional list res to store the dynamic frequency list.

Method 7: Using default dictionary and loop to generate frequency list

1. In this approach, we use a default dictionary to store the frequency of each character encountered in the list. 
2. We then loop over the list and append the frequency and character to a result list. 
3. We use the defaultdict to automatically initialize the frequency to 0 for any character not yet encountered in the list.

The original list is : ['z', 'z', 'e', 'f', 'f', 'e', 'f', 'z', 'c']
Dynamic Frequency list : ['1z', '2z', '1e', '1f', '2f', '2e', '3f', '3z', '1c']

Time complexity: O(n)
Auxiliary space: O(n)