String Verification Problems

0.Length of Last Word:
http://www.programcreek.com/2014/05/leetcode-length-of-last-word-java/

1.Maximum occuring character in a String:
Write an efficient C function to return maximum occurring character in the input string e.g., if input string is “test string” then function should return ‘t’.
http://www.geeksforgeeks.org/return-maximum-occurring-character-in-the-input-string/

2.First Repeating  & Non-Repeating character in a STRING

Variation 1: First non Repeating in a string
http://www.geeksforgeeks.org/given-a-string-find-its-first-non-repeating-character/
Variation 2: First non Repeating in a stream
http://www.geeksforgeeks.org/find-first-non-repeating-character-stream-characters/
Variation 3: String contains unique chars or not .
http://algorithms.tutorialhorizon.com/find-out-whether-string-contains-all-the-unique-characters/
Variation 4: First Repeating Char in a string
http://www.ritambhara.in/print-all-repeating-characters-in-a-string/

First Non Repeating character
The solution involves keeping track of what characters in the string have a count of more than one. The choice of data structure we will use depends on the type of string. If the string is an ASCII string with 256 possible values then an array of size 256 would be sufficient to track the count of each character. But, if the string is a Unicode string with 65536 possible character values and the input string was a small string (few characters wide), using an array would be inefficient . In the case where our input string is relatively small and the character set is large we can use a HashTable instead. If the loading factor of the Hashtable was selected to be high (to save memory) it could potentially suffer from collisions, but since out string is small the chances of collisions are less. On the other hand if the string was a long string and the character set was small the array based solution would be more efficient memory wise.
 Method 1-Array Method--O(n2)
int returnFirstNonRepeatedChar( char * str )
{
    int i,j, repeated = 0;
    int len = strlen(str);

    for( i = 0; i < len; i++ )
    {
        repeated = 0;
        for( j = 0; j < len; j++ )
        {
            if( i != j && str[i] == str[j] ) {
                repeated = 1;
                break;
            }
        }
        if( repeated == 0 ) {  // Found the first non-repeated character
            return i;
        }
    }
    return -1;
}

Method 2:Hash Table Method for Unicodes
Using binary search will not help. Though it looks like easiest way to improve search efficiency on a set of data is to put it in a data structure that allows more efficient searching. What data structures can be searched more efficiently than O(n)? Binary trees can be searched in O(log(n)). But it will not return the "first" non repeating element.

Using hashtable
A hash table could work really handy here. Although, with this approach, we do sacrifice space for runtime improvement. So we can create a hash table by sequentially reading all the characters in the string and keeping count of the number of times each character appears. Once we’ve created the hash table, we can sequentially read the entries to see which one has a count of one. What is the runtime of this algorithm? We have O(n) to create the hash table and another O(n) to read the entries. This results in a runtime of O(n) + O(n) = O(2n) = O(n).

Arrays and hashtables both have constant time element lookup. Begin by trying to take advantage of an array or hashtable because these data structures offer the greatest potential for improvement. You'll want to be able to quickly determine which data structure is better to use.

Hashtables have a higher lookup overhead than arrays. On the other hand, an array would initially contain random values that you would have to take time to set to zero, whereas a hashtable initially has no values. Perhaps the greatest difference is in memory requirements. An array would need an element for every possible value of a character. This would amount to a relatively reasonable 256 elements if you were processing ASCII strings, but if you had to process Unicode strings you would need more than 65,000 elements (Unicode uses 16-bit characters). In contrast, a hashtable would require storage for only the characters that actually exist in the input string. So, arrays are a better choice for long strings with a limited set of possible character values.
hashtables are more efficient for shorter strings or when there are
many possible character values.
Code:

// returns the index of the 1st non-repeated character in the input string
int Find_First_Non_Repeated_Char(string s)
{
     Hashtable ht = new Hashtable();

     // populate the hash table with count for each character in the string
     for(int i=0; i<s.Length; i++)
     {
        if(ht.Contains(s[i]))
        {
           int count = (int) ht[s[i]]; //get the count for the character
           ht[s[i]] = ++count;
        }
        else
        {
           ht[s[i]] = 1;
        }
     }

     // now go through the hash table one character at a time and find the  
     // one that has a count of 1
     
     for(int i=0; i< s.Length; i++)
     {
        if(ht.Contains(s[i]) && (int)ht[s[i]] == 1)
        {
           return i;
        }
     }
     return -1; // the input does not contain non-repeated character
}

First Repeating character

#include <stdio.h>
 
int main()
{
    unsigned long long int a = 0;
    char str[50];
    int i;
    int character[52]= {0};
 
    scanf ("%s", str);
    // variable 'a' keeps track of which character has
    // been already parsed.  
    for ( i = 0; str[i]; i++ ) {
        // check if the character is capital letter
        if ( str[i] >= 'A' && str[i] <= 'Z' ) {
            character[str[i]-'A']++;
            // Check to see if the character has already been parsed
            if ( (a & (1ULL << (str[i] - 'A'))) == 0 )
            {
                // if it's a new character then shift 1 by its
                // corresponding ascii value or'ed it with value in a.
                a |= (1ULL << (str[i] - 'A'));
                putchar (str[i]);
            }
            {
              if(character[str[i]-'A'] > 1)
                printf("\n %c First repeating character at %d\n", str[i], i);
            }
        }  // check if the character is small letter 
        else if ( str[i] >= 'a' && str[i] <= 'z' )
        {
            character[str[i]-'a' + 26]++;
            if ( (a & (1ULL << (str[i] - 'a' + 26))) == 0 )
            {
                // if it's a new character then shift 1 by its
                // corresponding ascii value or'ed it with value in a.                
                a |= (1ULL << (str[i] - 'a' + 26));
                putchar(str[i]);
            }
            {
               if(character[str[i]-'a' + 26] > 1)
                   printf("\n %c First repeating character at %d count %d\n",
str[i],  i,character[str[i]-'a' + 26]);
            }
        }
    }
    for ( i = 0; str[i]; i++ )
    {
         if ( str[i] >= 'A' && str[i] <= 'Z' )
         {
             if(character[str[i]-'A'] == 1)
             {
                break;
             }
         }
         else if(str[i] >= 'a' && str[i] <= 'z' )
         {
             if(character[str[i]-'a' + 26] == 1)
             {
                break;
             }
         }        
    }
    printf("First Non repeating character %c\n", str[i]);
    return 0;
}
Variation 1:
Determine if the string has all the unique characters:
Method 1:Using Hash
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

 bool isunique(char a[])
 {
        int i=0,t;
        bool b[256]; //Use of Boolean hash is better in terms of space
        for(i=0;i<256;i++) b[i]=0;
        i=0;
        while(a[i]!='\0')
        {
            t=a[i];

                if(b[t]==1)
                {
                    printf("Found Duplicate...\n");
                    return 0;
                }
            b[t]=1;
            i++;
        }
        printf("No duplicates...\n");
        return 1;

 }

 int main()
 {
        char a[]="santosh";
        printf("%d",isunique(a));
        return 1;
 }

Method 2:Using Bit Vector

#include <iostream>
#include <string.h>
#define MAX 100

void isstring(){
 char str[MAX] = "sudhansu";
 int checker = 0;
 
 for (int i = 0; i < strlen(str); ++i) 
 {
    int val = str[i] - 'a';
    if ((checker & (1 << val)) > 0)
     {
      printf("String contains duplicate characters\n");
      return;
     }
 checker |= (1 << val);
                }
 printf("String contains all unique characters\n");
 }
        
int main(){
   isstring();
   system("pause");
   return 0;
}

Strategy:

Let me explain what the above signifies:

‘checker’ is the bit vector. checker[i] = 0 if ASCII code ‘a’ + i has not been presented; 
1 otherwise. That is what line 6 is doing. | is inclusive OR (i.e., the general sense OR).

Within loop, compare wether a bit-position has already been filled (i.e.,value 1)This 
is done by logical and. That is what line 5 is doing. & is bitwise AND. << shifts the 
left-hand operand to right-hand bits to the left.

Alternate Methods:

1.Check every char of the string with every other char of the string for duplicate 
occurrences. This will take O(n^2) time and no space.

2.If we are allowed to destroy the input string, we could sort the string in O(n log n) 
time and then linearly check the string for 
neighboring characters that are identical. Careful, though – many sorting 
algorithms take up extra space.

4.Min Distance between two characters

public static int GetMinimumDistance(string str, char ch1, char ch2)
        {
            int distance = -1; int flag = 0; int x = -1; int y = -1;
            for (int i = 0; i < str.Length; i++)
            {
                if (str[i] == ch1 || str[i] == ch2)
                {
                    //Initialize
                    if (flag == 0)
                    {
                        if (str[i] == ch1)
                        {
                            flag = 1; x = i;
                        }
                        else
                        {
                            flag = 2; y = i;
                        }
                    }
                    else
                    {
                        //Encountered second character after first
                        if (flag == 1 && str[i] == ch2)
                        {
                            y = i; flag = 2;
                        }
                        //Encountered first character after second
                        else if (flag == 2 && str[i] == ch1)
                        {
                            x = i; flag = 1;
                        }
                        //Encountered first character again after first
                        else if (flag == 1 && str[i] == ch1)
                        {
                            x = i;
                        }
                        //Encountered second character again after second
                        else if (flag == 2 && str[i] == ch2)
                        {
                            y = i;
                        }
                    }
                    //Check Distance
                    if (x != -1 && y != -1)
                    {
                        if (distance == -1)
                        {
                            distance = Math.Abs(x - y);
                        }
                        else
                        {
                            if (distance > Math.Abs(x - y))
                            {
                                distance = Math.Abs(x - y);
                            }
                        }
                    }
                }
            }
            return distance;
        }
C Code:
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#define min(a,b) (a) < (b) ? (a) : (b)
int mindist(const char *s, const char a, const char b)
{
        if(!s || !*s)
                return INT_MAX;

        char lastchar = '\0',c;
        int lastpos, i = 0, m = INT_MAX;

        while((c = s[i]))
        {
                if((c == a) || (c == b))
                {
                        if((c == a && lastchar == b) || (c == b && lastchar == a))
                        {
                                m = min(m, i - lastpos);                  
                        }
                        lastchar = c;
                        lastpos = i;
                }
                i++;
        }
        return m;
}
int main()
{
        char s[256];
        scanf("%s\n", s);
        char  a, b;
        scanf("%c %c", &a, &b);

        int d;
        if((d = mindist(s, a, b)) != INT_MAX)
        {
                printf("%d\n", d);
        }
        system("pause");
        return 0;

}