Q-25 PepCoding | Group Shifted String
Thu Jan 26 2023 11:13:20 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
import java.util.*;
public class Main {
public static ArrayList<ArrayList<String>> groupShiftedStrings(String[] strs) {
//make difference between characters as key and group strings
HashMap<String , ArrayList<String>> map = new HashMap<>();
for(String temp : strs){
char arr[] = temp.toCharArray();
//if only single character its key will be blank or ""
String val = "";
for(int i =1 ;i < arr.length ; i++){
int value = (arr[i] - arr[i-1]);
//handle if value comes out to be negative eg: y-a
if(value < 0 )
value += 26 ;
val += value + "#";
}
val += "."; // for one character it will be "."
ArrayList<String> list = map.getOrDefault(val,new ArrayList<>());
list.add(temp);
map.put(val , list);
}
//making an answer arralist and traversing the hashmap and storing the answers
ArrayList<ArrayList<String>> ans = new ArrayList<>();
for(String temp : map.keySet()){
ans.add(map.get(temp));
}
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
String[] arr = new String[N];
for (int i = 0; i < N; i++) {
arr[i] = sc.next();
}
ArrayList<ArrayList<String>> shiftedGroup = groupShiftedStrings(arr);
for (ArrayList<String> lst : shiftedGroup) {
Collections.sort(lst);
}
shiftedGroup.sort(new ListComparator());
display(shiftedGroup);
}
// it is used to make the result unique
static class ListComparator implements Comparator<List<String>> {
@Override
public int compare(List<String> l1, List<String> l2) {
if (l1.size() != l2.size()) {
return l2.size() - l1.size();
}
String l1str = l1.get(0);
String l2str = l2.get(0);
return l1str.compareTo(l2str);
}
}
public static void display(ArrayList<ArrayList<String>> list) {
for (int i = 0; i < list.size(); i++) {
ArrayList<String> currList = list.get(i);
for (int j = 0; j < currList.size(); j++) {
System.out.print(currList.get(j) + " ");
}
System.out.println();
}
}
}
content_copyCOPY
https://www.pepcoding.com/resources/data-structures-and-algorithms-in-java-levelup/hashmap-and-heaps/group-shifted-string-official/ojquestion
Comments