[CSES] Creating Strings

2021-06-23

1 minute read

Algorithm

cses

Creating Strings

Task:

Given a string, your task is to generate all different strings that can be created using its characters.

Input

The only input line has a string of length $n$. Each character is between a–z.

Output

First print an integer $k$: the number of strings. Then print $k$ lines: the strings in alphabetical order.

Constraints

$1 \le n \le 8$

Example

Input:
aabac

Output:

20

aaabc

aaacb

aabac

aabca

aacab

aacba

abaac

abaca

abcaa

acaab

acaba

acbaa

baaac

baaca

bacaa

bcaaa

caaab

caaba

cabaa

cbaaa

Solutions:

Intuition: It's kinda back-tracking problem when generating all the possible results. The concerned point is that these results is needed to be presented in ascending order. Hmm, firstly, sorting the input array so that traveling operation is always remained in ascending order. Then do the same thing with solving a normal back-tracking problem. Tracking the visited node, checking whether the current character is valid or not, constructing a valid sub-result and storing to global result, go forward or go backwards when reaching the end of input array. At the end, print all of them.

Implementation:

 1def recur(length,ind,tmp,visited,str,res):
 2    tracking=[False]*25
 3    if ind<length:
 4    for i in range(len(str)):
 5        if not tracking[ord(str[i])-97] and not visited[i]:
 6            visited[i]=True
 7            recur(length,ind+1,tmp+str[i],visited,str,res)
 8            tracking[ord(str[i])-97]=True
 9            visited[i]=False
10        else:
11            res.append(tmp)
12
13def solve(str):
14    visited=[False]*len(str)
15    res=[]
16    str=sorted(str)
17    recur(len(str),0,"",visited,str,res)
18    print(len(res))
19    for i in res:
20        print(i)
21
22if __name__=="__main__" :
23    solve(input())

Analysis:

Time complexity: O(1).

Space complexity: O(1).