Detect the window length with highest number of distinct characters

In a string detect the window length with highest number of distinct characters.
For example if A = “aabcbcdbca”, then output should be 4 corresponding to sub string “dbca”.

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

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            //Smallest window with highest number of distinct characters
            string str = "aabcbcdbca";
            //Generate all substrings
            for (int i = str.Length; i > 0; i--) //Window length
            {
                for (int j = 0; j + i <= str.Length; j++) //Starting point
                {
                    string tempStr = str.Substring(j, i);
                    if (ContainsDistinctCharacters(tempStr))
                    {
                        Console.WriteLine("Length = " + tempStr.Length);
                        Console.WriteLine("String = " + tempStr);
                        i = 0; //Initialization to terminate the outer loop
                        break;
                    }
                }
            }   
        }
        public static bool ContainsDistinctCharacters (string str)
        {
            Hashtable ht = new Hashtable();
            for (int i = 0; i < str.Length; i++)
            {
                if(ht.Contains(str[i]))
                {
                    return false;
                }
                else
                {
                    ht.Add(str[i], 1);
                }
            }
            return true;
        }
    }
}

Output
=======
Length = 4
String = dbca
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s