Question

You will be given a string, containing both uppercase and lowercase alphabets(numbers are not allowed). You have to print all permutations of string with the added constraint that you can’t change the uppercase alphabets positions. Respond in Python please

Answer 1

val = input("Enter your String: ")  #taking the input string

result = []                # A list to store all the permutation of string without considering uppercase letter position
  
def permute(data, i, length):    # permute function to calculate all permutation
    if i == length:  
        result.append(''.join(data) ) 
    else:  
        for j in range(i, length):    # this method is bactracking approach to calculate permutation of string
            # swap 
            data[i], data[j] = data[j], data[i]    # swap
            permute(data, i + 1, length)                 # recusively call the function until all position is swaped
            data[i], data[j] = data[j], data[i]    # bactracking 
permute(list(val), 0, len(val)) 

res = []           # another list to store only those permutation which uppercase letter position does not changed
for s in result:      # loop throgh all string of the permutation list
    n = len(s)
    flag=0          # a flag variable to check if the String uppercase letter position does not changed with the given input string
    for i in range(0, n) :
        if (s[i]>='A' and s[i]<='Z') and s[i]!=val[i]: # if letter is uppercase and does not match position then flag=1 
           flag=1  # if flag==1 nit store that string in output result list
           break
    if flag==0:      
        if (s not in res):   # check if that string already present in the lis or not
            res.append(s)
        
for s in res:  # print all the string of output list res
    print(s)

Time complexity of this algorithm is O(n*n!) where n is the length of the string

Output: