Consider the following code snippet that generates all permutations of a given string:

def permute$($s$)$:

if len$($s$)==1$:

return $[$s$]$

result $=[]$

for i in range$($len$($s$))$:

c $=$ s$[$i$]$

rest $=$ s$[$:i$]+$ s$[$i $+1$:$]$

For p in permute$($rest$)$;

result.append$($ c $+$ p$)$

return result

Which of the following statements is TRUE about the time complexity of this algorithm?

$$ The time complexity is O$($n$),$ where n is the length of the input string.

$$ The time complexity is O$($n$^2),$ where n is the length of the input string.

$$ The time complexity is O$($n$!),$ where n is the length of the input string.

$$ The time complexity is O$(2^$n$),$ where n is the length of the input string.