How to efficiently find the least occurring character in a string ?

Question

I need O(N) solution where "N" is the length of the string  . String consists of lowercase english alphabets .

Answer 1

#Language - C#

#Below program can store all the least occuring characters in a string.

#Time Complexity - O(N)

Approach  : 

1. Created list to store the east occuring characters in a string and initialized temporary variable value to 1 (any character in string can occur at minimun once).

2. Iterated string and got the count of character using LINQ.

3. If the count of the character is less than or equal to temp variable, assign the count value to temp varibale and add that character to list.

 

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

public class Test
{
    public static void Main()
    {
        string s =Console.ReadLine().ToLower();
        List<char> list = new List<char>();
        int temp=1;
        char c =' ';
        for(int i=0;i<s.Length;i++)
        {
            int j = s.Where(t => t.Equals(s[i])).Count();
            if(j<=temp)
            {
              temp=j;
              list.Add(s[i]);
            }
        }
        
        foreach(var v in list)
        Console.WriteLine(v);
    }
}

Answer 2

This is very basic and famous approch whcih will find the answer in o(n)

Algorithm:

1. Keep a map of char and int which will be storing the occurance of charecter

2. Calculate the minimum value from that map

 

Program:

int fun(string s, int n){

    map<char, int> m;

    for(int i=0;i<n;i++){

        m[s[i]]++;

    }

    int min_value=INT_MIN;

    for(auto i:m){

       min_value  = min( min_value, i.second);

    }

    return min_value;

}

Answer 3

Approach  : 

1. Created an integer array of 26 for storing a count of character occurred in the string  there are 26 alphabet I had created an array of 26

2. After that, just iterated over a string and incremented an count of corresponding index value 

3. Iterated over an int array in order to find a character occur and min count

Complexity :

• Time complexity: O(n)

• Space Complexity : O(26) -------- Constant space complexity

Code : Java 8 code

 

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) {
        int arr[] = new int[26];
        String s= "Javvva";
        s = s.toLowerCase();
        Arrays.fill(arr, 0);
//        System.out.println((int)s.charAt(0)+" "+s.charAt(0));

        for(int i=0;i<s.length();i++) {
            if(arr[(int)s.charAt(i)-(int)'a'] > 0) {
                arr[(int)s.charAt(i)-(int)'a']++;
            }else {
                arr[(int)s.charAt(i)-(int)'a']=1;
            }
        }
        int min = Integer.MAX_VALUE;
        int index=-1;
        for(int i=0;i<26;i++){
            if(arr[i]!=0 && min > arr[i]) {
                min = arr[i];
                index = i;
            }
        }
        System.out.println("character occur = "+(char)((int)'a'+index)+" "+" mincount = "+min);
    }
}