Python counter and dictionary intersection example (Make a string using deletion and rearrangement)

Last Updated : 21 Aug, 2022

Given two strings, find if we can make first string from second by deleting some characters from second and rearranging remaining characters.

Examples:

Input : s1 = ABHISHEKsinGH
      : s2 = gfhfBHkooIHnfndSHEKsiAnG
Output : Possible

Input : s1 = Hello
      : s2 = dnaKfhelddf
Output : Not Possible

Input : s1 = GeeksforGeeks
      : s2 = rteksfoGrdsskGeggehes
Output : Possible

We have existing solution for this problem please refer Make a string from another by deletion and rearrangement of characters link. We will this problem quickly in python. Approach is very simple,

Convert both string into dictionary using Counter(iterable) method, each dictionary contains characters within string as Key and their frequencies as Value.
Now take intersection of two dictionaries and compare resultant output with dictionary of first string, if both are equal that means it is possible to convert string otherwise not.

Implementation:

Python3

# Python code to find if we can make first string
# from second by deleting some characters from
# second and rearranging remaining characters.
from collections import Counter
 
def makeString(str1,str2):
 
    # convert both strings into dictionaries
    # output will be like str1="aabbcc",
    # dict1={'a':2,'b':2,'c':2}
    # str2 = 'abbbcc', dict2={'a':1,'b':3,'c':2}
    dict1 = Counter(str1)
    dict2 = Counter(str2)
 
    # take intersection of two dictionaries
    # output will be result = {'a':1,'b':2,'c':2}
    result = dict1 & dict2
 
    # compare resultant dictionary with first
    # dictionary comparison first compares keys
    # and then compares their corresponding values
    return result == dict1
 
# Driver program
if __name__ == "__main__":
    str1 = 'ABHISHEKsinGH'
    str2 = 'gfhfBHkooIHnfndSHEKsiAnG'
    if (makeString(str1,str2)==True):
        print("Possible")
    else:
        print("Not Possible")

Output

Possible

Time Complexity: O(n)

Auxiliary Space: O(1)

S

Shashank Mishra

Improve

Make a string from another by deletion and rearrangement of characters

Similar Reads

Python - Counter.items(), Counter.keys() and Counter.values()

Counter class is a special type of object data-set provided with the collections module in Python3. Collections module provides the user with specialized container datatypes, thus, providing an alternative to Python’s general-purpose built-ins like dictionaries, lists and tuples. Counter is a sub-class that is used to count hashable objects. It imp

Make a string from another by deletion and rearrangement of characters

Given two strings, find if we can make first string from second by deleting some characters from second and rearranging remaining characters. Examples: Input : s1 = ABHISHEKsinGH, s2 = gfhfBHkooIHnfndSHEKsiAnGOutput : Possible Input : s1 = Hello, s2 = dnaKfhelddfOutput : Not Possible Input : s1 = GeeksforGeeks, s2 = rteksfoGrdsskGeggehesOutput : Po

Minimize swaps of adjacent characters to sort every possible rearrangement of given Binary String

Given a binary string S of length N consisting of 0s, 1s, and "?", where "?" can be replaced by either 0 or 1, the task is to count the sum of minimum swaps of adjacent characters required to sort every possible arrangement of the string in non-decreasing order Since the answer can be very large, print it modulo 109 + 7. Examples: Input: S = "?0?"O

Python dictionary, set and counter to check if frequencies can become same

Given a string which contains lower alphabetic characters, we need to remove at most one character from this string in such a way that frequency of each distinct character becomes same in the string. Examples: Input : str = “xyyz” Output : Yes We can remove character ’y’ from above string to make the frequency of each character same. Input : str =

Dictionary and counter in Python to find winner of election

Given an array of names of candidates in an election. A candidate name in the array represents a vote cast to the candidate. Print the name of candidates received Max vote. If there is tie, print a lexicographically smaller name. Examples: Input : votes[] = {"john", "johnny", "jackie", "johnny", "john", "jackie", "jamie", "jamie", "john", "johnny",

Using Counter() in Python to find minimum character removal to make two strings anagram

Given two strings in lowercase, the task is to make them Anagram. The only allowed operation is to remove a character from any string. Find minimum number of characters to be deleted to make both the strings anagram? If two strings contains same data set in any order then strings are called Anagrams. Examples: Input : str1 = "bcadeh" str2 = "hea" O

Maximize the Median of Array formed from adjacent maximum of a rearrangement

You are given X[] of length 2*N, Where N will always be odd, the task is to construct an array Y[] of length N from a rearrangement of X[] such that Y[]'s element is equal to max(Xi, Xi+1) and i is always an even index (0 based indexing), and the median of the new array is maximum possible. Examples: Input: N = 1, X[] = {1, 2} Output: X[] = {2, 1},

Maximise product of each array element with their indices by rearrangement

Given an Array of N integers, the task is to maximize the value of the product of each array element with their corresponding indices by rearranging the array. Examples: Input: N = 4, arr[] = { 3, 5, 6, 1 }Output: 31Explanation: If we arrange arr[] as { 1, 3, 5, 6 }. Sum of arr[i]*i is 1*0 + 3*1 + 5*2 + 6*3 = 31, which is maximum Input: N = 2, arr[

Rearrangement of a number which is also divisible by it

Given a number n, we need to rearrange all its digits such that the new arrangement is divisible by n. Also, the new number should not be equal to x. If no such rearrangement is possible, print -1. Examples: Input : n = 1035 Output : 3105 The result 3105 is divisible by given n and has the same set of digits. Input : n = 1782 Output : m = 7128 Simp

Count lexicographically smallest subsequences after rearrangement

Given a string S of length N, then your task is to find number of subsequences Y of string S such that: Y must be non-empty string and Y must be lexicographically smallest among all the possible strings obtained by rearranging the characters of Y.Examples: Input: N = 2, S = "ju"Output: 3Explanation: Three possible strings can be: {"j", "u", "ju"}.

Article Tags :

Practice Tags :