Find all permutation of a string in another string

Question

I have a string, for example: string1 = 'abcdbcabdcabb'. And I have another string, for example: string2 = 'cab'

I need to count all permutation of string2 in string1.

Currently I'm adding all permutation of string2 to a list, and than iterating threw string1 by index+string.size and checking if sub-string of string1 contain in the list of the permutations

I'm sure there is a better optimized way to do it.

Answer 1

You do not need DP in my mind, but a sliding window technic. A permutation of string2 is a string that has exactly the same length and the distribution of the characters is the same. In your example of string2, a permutation is. a string of length 3 with this distribution of characters: {a:1,b:1,c:1}.

So you can write a script, to consider a window of size N (size of string2), from the beginning of string1(index=0). if your current window has exactly the same distribution of characters, you accept it as a permutation, if not you do not count it, and you move on to index+1.

A trick for not recalculating the character distribution in each sliding window, you can get a dictionary of characters, and count the characters at the very first window, then when you slide the window one to the right, you decrease the removing character by one, and increase the adding character by 1.

The code should be something like this, you need to verify it for edge cases:

def get_permut(string1,string2):
 N =len(string2)
 M = len(string1)
 if M < N:
 return 0
 valid_dist = dict()
 for ch in string2:
 valid_dist.setdefault(ch,0)
 valid_dist[ch]+=1
 
 current_dist=dict()
 for ch in string1[:N]:
 current_dist.setdefault(ch,0)
 current_dist[ch]+=1
 
 ct=0
 for i in range(M-N):
 if current_dist == valid_dist:
 ct+=1
 current_dist[i]-=1
 current_dist.setdefault(i+1,0)
 current_dist[i+1]+=1
 if current_dist[i]==0:
 del current_dist[i]
 
 return ct
 

• flakes: Excellent answer!
• SilverCrow: Great answer. but I think there is an error in the last for loop current_dist[i]-=1, you are trying to access an index(int) but a key is needed. getting KeyError when im trying to run the function
• alift: @SilverCrow I made a correction, please check again. As I have said, I shared the code only to give you a big picture of the algorithm. Up to you to check the edge cases. Good luck!

Answer 2

You can use string.count() method here. See below for some way to resolve it:

import itertools
perms=[''.join(i) for i in itertools.permutations(string2)]
res=0
for i in perms:
 res+= string1.count(i)
print(res)
# 4

Answer 3

You can use regex for that.

def lst_permutation(text):
 from itertools import permutations
 lst_p=[]
 for i in permutations(text):
 lst_p.append(''.join(i))
 return lst_p
def total_permutation(string1,string2):
 import re
 total=0
 for i in lst_permutation(string2):
 res=re.findall(string2,string1)
 total += len(res)
 return total
string1 = 'abcdbcabdcabb'
string2 = 'cab'
print(total_permutation(string1,string2))
#12

• flakes: Might be good to do re.findall(re.escape(string1), string2) in case the search string contains valid regex text.
• IoaTzimas: This doesn't count all permutations of string2
• neilharia7: This won't work, as abc is a permutation for cab which won't be captured

Answer 4

Here's a dumb way to do it with a regex (don't actually do this).

Use a non capturing group for each letter in the search text, and then expect one of each captured group to appear in the output:

import re
string1 = 'abcdbcabdcabb'
string2 = r'(?:c()|a()|b()){3}1円2円3円'
pos = 0
r = re.compile(string2)
while m := r.search(string1, pos=pos):
 print(m.group())
 pos = m.start() + 1

abc
bca
cab
cab

Can also dynamically generate it

import re
string1 = 'abcdbcabdcabb'
string2 = 'cab'
before = "|".join([f"{l}()" for l in string2])
matches = "".join([f"\\{i + 1}" for i in range(len(string2))])
r = re.compile(f"(?:{before}){{{len(string2)}}}{matches}")
pos = 0
while m := r.search(string1, pos=pos):
 print(m.group())
 pos = m.start() + 1