C# - use Next Permutation to permute half the string at each iteration


  • 0

    the idea is to find the characters that will go into the left half of the sting. Start with the lowest permutation for this set, then go to next permutation until at highest permutation and stop. At each permutation found build the result string by concatenating the permutation, the mid char and the reverse of the permutation.

        public IList<string> GeneratePalindromes(string s)
        {            
            int[] map = new int[256];
            foreach (char c in s) map[c]++;
    
            // consider only left half of Palindrome
            // find first permutation of left half, find possible mid char
            bool hasMidChar = false;
            char midChar = '0';
            char[] leftChars = new char[s.Length / 2];
            int leftPos = 0;
            for (int i = 0; i < map.Length; i++)
            {
                while (map[i] > 1)
                {
                    map[i] -= 2;
                    leftChars[leftPos++] = (char)i;
                }
                if (map[i] == 1)
                {
                    // already a different mid char, no palindromes possible
                    if (hasMidChar) return new List<string>();
    
                    // this is your mid char
                    hasMidChar = true;
                    midChar = (char)i;
                }
            }
    
            IList<string> list = new List<string>();
    
            // add each permuation to list
            // permute left side, right side is just reversal of left side
            do
            {
                StringBuilder sb = new StringBuilder();
                sb.Append(leftChars);
                if (hasMidChar) sb.Append(midChar);
                for (int i = leftChars.Length - 1; i >= 0; i--) sb.Append(leftChars[i]);
                list.Add(sb.ToString());
            }
            while (PermuteNext(leftChars));
    
            return list;
        }
    
        public bool PermuteNext(char[] chars)
        {
            // find first decreasing char from end going backwards
            int curr = chars.Length - 1;
            while (curr > 0 && chars[curr - 1] >= chars[curr]) curr--;
    
            // already sorted in reverse order, no increasing next
            if (curr <= 0) return false;
    
            // find elem to swap with new head
            int swapWith = curr;
            while (swapWith < chars.Length - 1 && chars[curr - 1] <= chars[swapWith + 1]) swapWith++;
    
            Swap(chars, curr - 1, swapWith);
    
            // reverse chars to right to bring to lowest permuation with this new head
            for (int i = curr, j = chars.Length - 1; i < j; i++, j--) Swap(chars, i, j);
    
            return true;
        }
    
        public void Swap(char[] chars, int i, int j)
        {
            char temp = chars[i];
            chars[i] = chars[j];
            chars[j] = temp;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.