PROBLEM DESCRIPTION
Given a string A with lowercase english alphabets and you have to return a string in which, with each character its frequency is written in adjacent.
SOLUTION
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
public class Solution {
public String solve(String A) {
int n = A.length();
int[] freq = new int[26];
// get current character and increase its frequency
for(int i=0; i<n; i++){
char ch = A.charAt(i);
// ch - 'a' will map the characters based on 0 index in the array
freq[ch - 'a']++;
}
StringBuffer sb = new StringBuffer();
Set<Character> visited = new HashSet<>();
// for each character in the given string
for(int i=0; i<n; i++){
// get current char
char ch = A.charAt(i);
// if its frequency was not already notes earlier
if(!visited.contains(ch)){
// add the current char and its freq
sb.append(String.valueOf(ch));
sb.append(String.valueOf(freq[ch-'a']));
// mark as visited
visited.add(ch);
}
}
return sb.toString();
}
}
SMALL SPACE OPTIMIZATION
Instead of using HashSet to track the visited array, we can reuse the exiting frequency array itself. We can get the current character. If its frequency is more than 0, append it to the answer String. Also, set its frequency to 0. If we do this, when we encouter the same character again, it will not get appended again, since its frequency is now 0.
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
public class Solution {
public String solve(String A) {
int n = A.length();
int[] freq = new int[26];
for(int i=0; i<n; i++){
char ch = A.charAt(i);
freq[ch - 'a']++;
}
StringBuffer sb = new StringBuffer();
for(int i=0; i<n; i++){
char ch = A.charAt(i);
// if freq of current char is more than 0
if(freq[ch-'a'] > 0){
sb.append(String.valueOf(ch));
sb.append(String.valueOf(freq[ch-'a']));
// set the freq of current char to 0
// this will avoid appending it again if there are duplicates
freq[ch-'a'] = 0;
}
}
return sb.toString();
}
}