Lexicographically Sort String Array

Question

I've been working on a challenge and have researched it for several hours and am still having trouble how to "properly" sort a string array or list of string in lexicographical order in C#.

The problem of the challenge I'm working:

Take into account only the lower case letters of two strings.
Compare them to find out which characters occur in both strings.
Compare those characters and find out which of the original strings contains the most occurrences of each character.
Append the result as a string in a format that depicts which string has the higher count "1:" or "2:" or if equal "=:" followed by all the characters in that string joined by "/".
Sort the result in decreasing order of their length, and when they are of equal lengths sort the substrings in ascending lexicographic order.

An example of the result is and below it is my output:

"2:eeeee/2:yy/=:hh/=:rr"

"2:eeeee/2:yy/=:rr/=:hh"

Another example of a correct result is and below it is my output:

1:ooo/1:uuu/2:sss/=:nnn/1:ii/2:aa/2:dd/2:ee/=:gg

=:nnn/1:ooo/1:uuu/2:sss/=:gg/1:ii/2:aa/2:dd/2:ee

The line of code that is causing this is:

strings = strings.OrderByDescending(x => x.Length).ThenBy(c => c).ToArray();

I've tried different ways of approaching this problem such as splitting the string into individual string arrays of certain lengths, perform a lexicographic order, then append them back into the result. But with the many different test cases, one would pass and the other would fail.

My issue is finding out why C# sees "=" as LESS THAN digits, when really it's greater on the ASCII chart. I ran a test and that is what String.Compare gave me. In Python, it gave me something different.

Here is my complete code, feel free to point out any bugs. I've only been programming for 9 months. I am aware it isn't the best solution.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Rextester
{
    public class Program
    {
        public static void Main(string[] args)
        {
            string s1 = "looping is fun but dangerous";
            string s2 = "less dangerous than coding";

            // Expected
            Console.WriteLine("1:ooo/1:uuu/2:sss/=:nnn/1:ii/2:aa/2:dd/2:ee/=:gg\n");

            // Result
            Console.WriteLine(StringsMix(s1, s2));
        }

        public static string StringsMix(string s1, string s2)
        {
            StringBuilder sb = new StringBuilder();
            // Convert string to char arrays order by ascending
            char[] s1Chars = s1.Where(x => char.IsLower(x)).OrderBy(x => x).ToArray();
            char[] s2Chars = s2.Where(x => char.IsLower(x)).OrderBy(x => x).ToArray();

            // Insert arrays to find characters that appear in both 
            char[] inter = s1Chars.Intersect(s2Chars).ToArray();

            for (int i = 0; i < inter.Length; i++){
                // For each character, put all occurences in their respective array
                // Get count
                char[] s1Ch = s1.Where(x => x.Equals(inter[i])).ToArray();
                char[] s2Ch = s2.Where(x => x.Equals(inter[i])).ToArray();
                int s1Count = s1Ch.Length;
                int s2Count = s2Ch.Length;

                if (s1Count > s2Count)
                {
                    string chars = new String(s1Ch);
                    sb.Append("1:" + chars + "/");
                }
                else if (s2Count > s1Count)
                {
                    string chars = new String(s2Ch);
                    sb.Append("2:" + chars + "/");
                }
                else if (s1Count == s2Count)
                {
                    string chars = new String(s1Ch);
                    sb.Append("=:" + chars + "/");
                }
            }

            string final = String.Empty;
            string[] strings = sb.ToString().Split('/');
            strings = strings.OrderByDescending(x => x.Length).ThenBy(c => c).ToArray(); // "Lexicographical ordering"

            final = String.Join("/", strings);
            strings = final.Split('/').Where(x => x.Length > 3).Select(x => x).ToArray(); // Remove trailing single characters
            final = String.Join("/", strings);
            return final;
        }
    }
}

Note that OrderBy accepts string comparer as second parameter. If you don't provide it - it will sort according to the current culture rules. — Evk
– Evk, Commented Dec 14, 2017 at 22:03

Sergey Kalinichenko · Accepted Answer · 2017-12-14 21:04:53Z

1

This happens because '=' sorts before '1' and '2'; you want it to sort after the digits.

You can force this order by adding a special condition in the middle:

var specialOrder = "12=";
var ordered = data
    .OrderByDescending(s => s.Length)
    .ThenBy(s => specialOrder.IndexOf(s[0])) // <<== Add this
    .ThenBy(s => s);

This will ensure that the initial character sorts according to the order of characters in specialOrder string, i.e. '1', then '2', then '='.

Demo.

Note: The code makes an assumption that the sequence has no empty strings. Your code ensures that each string has at least three characters, so it is not a problem.

answered Dec 14, 2017 at 21:04

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

hackexe Over a year ago

So close, I received an IndexOutOfRangeException.

Sergey Kalinichenko Over a year ago

@HackerExecute This means you have an empty string in there.

hackexe Over a year ago

I got it working, thank you so much for the help brother!

Collectives™ on Stack Overflow

Lexicographically Sort String Array

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related