Permutation of a string backtracking

#Method 1: It includes even duplicates
#Better to go to method 2
def permute(s):
    s=list(s)
    n,ans=len(s),[]
    def dfs(i):
        if i==n-1:
            ans.append(''.join(s))
            return
        # we will swap indices from i+1 to n with i and do backtrack. This ensures generations of diff permutatations
        #In recursion level 1 we do swapping from 0th index to  (0+1,n) indices
        #in recursion level 2 we do swapping from 1st index to (1+1,n) indices
        #in recursion level ith we do swaping from ith index to (i+1,n) indices
        for j in range(i+1,n):
            s[i],s[j]=s[j],s[i]
            dfs(i+1)
            s[i],s[j]=s[j],s[i]
    dfs(0)
    return ans
permute("shpdwa")
#Method 2:No duplicates
'''
Why this works.
Since hashmap stores multiple counts of single same character.
So all keys in dict are unique.
When we do backtracking with these keys we can avoid duplicates.
E.g. (1,1) without hashmap it creates 2 partitions (1,1)(1,1)
But dictionary has {1:2}
keys=(1) . so only one pemutation happens
try with one more e.g. (1,2,2) you can understand easily
'''
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        freq={}
        res=[]
        perm=[]
        for i in nums:
            freq[i]=freq.get(i,0)+1
        def dfs():
            if len(perm)==len(nums):
                res.append(perm[:])
                return
            else:
                for key in freq.keys():
                    if freq[key]>0:
                        freq[key]-=1
                        perm.append(key)
                        dfs()
                        perm.pop()
                        freq[key]+=1
            return res
        return dfs()