11/180: Data Structure Problem Solving LeetCode

Given a non-empty string containing an out-of-order English representation of digits 0-9, output the digits in ascending order.

Note:

1. Input contains only lowercase English letters.
2. Input is guaranteed to be valid and can be transformed to its original digits. That means invalid inputs such as “abc” or “zerone” are not permitted.
3. Input length is less than 50,000.

Example 1:

Input: "owoztneoer"
Output: "012"

Example 2:

Input: "fviefuro"
Output: "45"

Solution:

Brute Force Approach:

This solution was made by me but it wasn’t time optimized, so I have to see the answer how to actually solve this problem in timely manner.

class Solution {
   
    
    public HashMap<Integer, String> getMap(){
        HashMap<Integer, String> map = new HashMap<>();
        map.put(0, "zero");
        map.put(1, "one");
        map.put(2, "two");
        map.put(3, "three");
        map.put(4, "four");
        map.put(5, "five");
        map.put(6, "six");
        map.put(7, "seven");
        map.put(8, "eight");
        map.put(9, "nine");
        return map;
    }
    public List<Character> stringToCharSet(String s){
        List<Character> set = new LinkedList<>();
        for(char c: s.toCharArray()){
            set.add(c);
        }
        return set;
    }
    
    public Boolean containsAllCharacter(String input, String mapValue){
return stringToCharSet(input).containsAll(stringToCharSet(mapValue));
        
    }
    
    public String originalDigits(String input) {
        String output = "";
   while(!input.isEmpty()){
      for(int i=0; i<10; i++){
          String mapValue = this.getMap().get(i);
          Boolean charExists = this.containsAllCharacter(input, mapValue);
          if(charExists == true){
                List<Character> set = stringToCharSet(mapValue);
                for(Character c : set){
                    input = input.replaceFirst(String.valueOf(c), "");
                    System.out.println(String.valueOf(c) + input);
                }
                output = output + Integer.toString(i);
          }
      }
   }
        return output;
    }
}

Optimized Solution:

//This solution is quite easy, there was a catch, because we already know there are 0 to 9 only, we first checked out unique letters in the string , like for Z, it appears only in zero, W it apears only in two. It means that if w or z appears we already knew which value is available in the string

class Solution {
    public String originalDigits(String s) {
        int[] count = new int[26];
        for(char c : s.toCharArray())
            count[c-'a']++;
        int[] num = new int[10];
        
        num[0] = count['z'-'a'];
        num[2] = count['w'-'a'];
        num[4] = count['u'-'a'];
        num[6] = count['x'-'a'];
        num[8] = count['g'-'a'];
        num[1] = count['o'-'a']- num[0]-num[2]-num[4];
        num[3] = count['h'-'a'] - num[8];
        num[5] = count['f'-'a'] -num[4];
        num[7] = count['s'-'a'] - num[6];
        num[9] = count['i'-'a']-num[5]-num[6]-num[8];
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<10; i++){
            while(num[i]-- > 0)
                sb.append(i);
            
        }
        
        return sb.toString();
        
    }
}

Below is the another question which I was able to solve without any help so I consider it as easy one

Alice has n candies, where the ith candy is of type candyType[i]. Alice noticed that she started to gain weight, so she visited a doctor.

The doctor advised Alice to only eat n / 2 of the candies she has (n is always even). Alice likes her candies very much, and she wants to eat the maximum number of different types of candies while still following the doctor's advice.

Given the integer array candyType of length n, return the maximum number of different types of candies she can eat if she only eats n / 2 of them.

Example 1:

Input: candyType = [1,1,2,2,3,3]
Output: 3
Explanation: Alice can only eat 6 / 2 = 3 candies. Since there are only 3 types, she can eat one of each type.

Example 2:

Input: candyType = [1,1,2,3]
Output: 2
Explanation: Alice can only eat 4 / 2 = 2 candies. Whether she eats types [1,2], [1,3], or [2,3], she still can only eat 2 different types.

Example 3:

Input: candyType = [6,6,6,6]
Output: 1
Explanation: Alice can only eat 4 / 2 = 2 candies. Even though she can eat 2 candies, she only has 1 type.

Constraints:

• n == candyType.length
• 2 <= n <= 104
• n is even.
• -105 <= candyType[i] <= 105

Took set data structure to store all unique candy types. And if the size of set is smaller than the half of the candies, then I will return the set size as Alice can only have one candy of each type otherwise we will return the length/2 of candyType array.

class Solution {
    public int distributeCandies(int[] candyType) {
     Set<Integer> set = new HashSet<>();
        for(int i = 0; i<candyType.length; i++){
            set.add(candyType[i]);
        }
        int setSize = set.size();
        int sizeOfHalfCandies = candyType.length / 2;
        if(sizeOfHalfCandies >= setSize)
           return setSize;
        else{
            return sizeOfHalfCandies;
        }
        }
    
}

PS: I wrote this yesterday, but somehow missed to post it. So posting it today.