Find all permutation of a string in another string

user_2693474 0
Viewed 393

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.

dynamic-programming algorithm python
4 Answers

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
user_110653470

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
user_82285580

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
user_119532660

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
user_32805380
Related