-
Notifications
You must be signed in to change notification settings - Fork 0
/
Better String.java
55 lines (30 loc) · 882 Bytes
/
Better String.java
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
class Solution {
public static String betterString(String str1, String str2) {
// Code here
int res1 = distinctSubsequences(str1);
int res2 = distinctSubsequences(str2);
// System.out.println(res1+" "+res2);
if(res1>=res2) return str1;
return str2;
}
static int distinctSubsequences(String S) {
// code here
int n = S.length();
int arr[] = new int[26];
Arrays.fill(arr,-1);
int ans = 0, diff = 0;
for(int i=0; i<n; i++){
int x = S.charAt(i)-'a';
if(i==0){
ans = 1;
arr[x] =1;
continue;
}
diff = 1+ans;
if(arr[x]==-1) ans = ans+diff;
else ans = ans+diff-arr[x];
arr[x] = diff;
}
return ans+1;
}
}