Print All Permutations of a String

Given an input string STR, generate and print all possible permutations of the string.

Input:

str

Output:

All permutations of the input string, each on a new line.

Example:

Input:

"abc"

Output:

abc
acb
bac
bca
cab
cba

Constraints:

• The input string STR consists only of lowercase alphabets.
• 1 ≤ length of STR ≤ 8
• Time Limit: 1 second

Note:

The input string may contain duplicate characters, resulting in duplicate permutations. The order of the permutations does not matter.