Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
1,800 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 (110,880 points) | 1,800 views

3 Answers

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
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
edited by anonymous
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