Brace Expansion: a popular interview question

One of the most popular interview questions - brace expansion, here it is: https://leetcode.com/problems/brace-expansion/

A string S represents a list of words.

Each letter in the word has 1 or more options.  If there is one option, the letter is represented as is.  If there is more than one option, then curly braces delimit the options.  For example, "{a,b,c}" represents options ["a", "b", "c"].

For example, "{a,b,c}d{e,f}" represents the list ["ade", "adf", "bde", "bdf", "cde", "cdf"].

Return all words that can be formed in this manner, in lexicographical order.

Example 1:

Input: "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]

Example 2:

Input: "abcd"
Output: ["abcd"]

Note:

1. 1 <= S.length <= 50
2. There are no nested curly brackets.
3. All characters inside a pair of consecutive opening and ending curly brackets are different

The idea is to just perform a DFS recursive call processing the brackets in a special manner:
 - Gather all the chars within the brackets
 - Add them all to a sorted data structure
 - Then use the sorted data structure to continue the DFS

Works relatively fast. Code is down below, cheers, ACC.

public class Solution
{
    public string[] Expand(string S)
    {
        LinkedList<string> retVal = new LinkedList<string>();
        Process(S, "", retVal);
        return retVal.ToArray<string>();
    }

    private void Process(string input,
                            string current,
                            LinkedList<string> retVal)
    {
        if (String.IsNullOrEmpty(input))
        {
            if (!String.IsNullOrEmpty(current)) retVal.AddLast(current);
            return;
        }

        if (!input.StartsWith("{"))
        {
            Process(input.Substring(1), current + input[0].ToString(), retVal);
        }
        else
        {
            SortedList<char, char> sortedChars = new SortedList<char, char>();
            int indexEnd = 1;
            for (; input[indexEnd] != '}'; indexEnd++)
            {
                if (input[indexEnd] != ',')
                {
                    sortedChars.Add(input[indexEnd], input[indexEnd]);
                }
            }
            indexEnd++;

            foreach (char key in sortedChars.Keys)
            {
                Process(input.Substring(indexEnd), current + key.ToString(), retVal);
            }
        }
    }
}