DSA/Hashmap.java at main · ShreyashDesai021/DSA · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
import java.util.*;

public class Hashmap{

    public static int firstUniqChar(String s) {

        HashMap<Character,Integer> map = new HashMap<>();

        for(int i = 0;i < s.length();i++){
            Character ch = s.charAt(i);
            map.put(ch,map.getOrDefault(ch,0)+1);
        }

        for(int i = 0;i < s.length();i++){
            if(map.getOrDefault(s.charAt(i),0) == 1){
                return i;
            }
        }

        return -1;
    }

// Below method use O(n) space complexity and O(n) time complexity, but it works for all characters.
    public static boolean canConstruct(String ransomNote, String magazine) {
        HashMap<Character,Integer> map = new HashMap<>();

        for(int i = 0;i < magazine.length();i++){
            char ch = magazine.charAt(i);
            map.put(ch,map.getOrDefault(ch,0)+1);
        }

        for(int i = 0;i < ransomNote.length();i++){
            char ch = ransomNote.charAt(i);
            if(map.containsKey(ch)){
                map.put(ch,map.getOrDefault(ch,0)-1);
                if(map.get(ch) == 0){
                    map.remove(ch);
                }
            }else{
                return false;
            }
        }

        return true;
    }


// Below method use O(1) space complexity and O(n) time complexity, but it only works for lowercase letters a-z.
    // public static boolean canConstruct(String ransomNote, String magazine) {
    //     int[] freq = new int[26];

    //     for (char ch : magazine.toCharArray()) {
    //         freq[ch - 'a']++;
    //     }

    //     for (char ch : ransomNote.toCharArray()) {
    //         if (--freq[ch - 'a'] < 0) {
    //             return false;
    //         }
    //     }

    //     return true;
    // }

    public static int maxNumberOfBalloons(String text) {

        HashMap<Character,Integer> map = new HashMap<>();

        for(int i = 0; i < text.length();i++){
            char ch = text.charAt(i);

            map.put(ch,map.getOrDefault(ch,0)+1);

        }

        int b = map.getOrDefault('b', 0);
        int a = map.getOrDefault('a', 0);
        int l = map.getOrDefault('l', 0) / 2; // "balloon" needs 2 'l's, so divide the count by 2. Integer division floors the result (5/2 = 2)
        int o = map.getOrDefault('o', 0) / 2;
        int n = map.getOrDefault('n', 0);

        return Math.min(b,Math.min(a,Math.min(l,Math.min(o, n))));

    }

    public static int longestPalindrome(String s) {
        HashMap<Character,Integer> map = new HashMap<>();

        for(int i = 0;i < s.length();i++){
            char ch = s.charAt(i);
            map.put(ch,map.getOrDefault(ch,0)+1);
        }

        int length = 0;
        boolean oddFlag = false;

        for(int freq : map.values()){
            if(freq % 2 == 0){
                length += freq;  // for even times appearing character we can take it completely in for palindrome
            }else{
                length += freq - 1;
                oddFlag = true;
            }
        }

        if(oddFlag){
            length += 1;
        }

        return length;


    }

    public static void main(String[] args) {
        System.out.println(firstUniqChar("leetcode")); // Output: 0

        System.out.println(canConstruct("aa", "aab")); // Output: true

        System.out.println(maxNumberOfBalloons("loonbalxballpoonl")); // Output: 2

        System.out.println(longestPalindrome("abccccdd")); // Output: 7
    }
}