0 like 0 dislike
137 views
I need O(N) solution where "N" is the length of the string  . String consists of lowercase english alphabets .
in Algorithms and Problems by Expert (15,650 points) | 137 views

3 Answers

1 like 0 dislike

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);
    }
}
by Expert (720 points)
0 like 0 dislike
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;

}
by (230 points)
0 like 0 dislike

#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);
    }
}

by Expert (980 points)