# Java n*(k*log(k)) AC PriorityQueue solution, where k<=n and k close to n/26 by average.

• The idea is to link each string's lexicographical biggest one first. At the same time, find the maximum char.
From each maximum char, we can start a string and these `k` strings are then put into the PriorityQueue to compare their first char and then move to the next char.

The time complexity is `n*k*log(k)`, where `k` is the number of strings starting with maximum char. Therefore, the worst case will be `n*n*log(n)` if all the char in the given strings are all the same. However, by average, if there are only 26 possible characters, 'a' to 'z', in the strings, then `k` should close to `n/26` initially. In addition, `k` should decrease by `1/26` after each loop until `k==1`. As a result, `k*log(k) < n` => `n*k*log(k) < n*n`.
The space complexity is O(k) because the `Node` object stores the pointer of a linked string which is not an actual String object.

``````public class Solution {
String reverse(String str) {
StringBuilder sb = new StringBuilder(str);
return sb.reverse().toString();
}
class Node {
String[] strs;
int from, from_idx, cur, cur_idx;
String fromStr, curStr;
char cur_char;
boolean started = false;
Node(String[] strs, int from, int from_idx, String fromStr){
this.strs = strs;
this.from = from;
this.from_idx = from_idx;
this.fromStr = fromStr;
cur = from;
curStr = fromStr;
cur_idx = from_idx;
cur_char = curStr.charAt(cur_idx);
}
boolean next(){
if (cur_idx==curStr.length()-1) {
cur_idx=0;
cur = cur+1 == strs.length ? 0 : cur+1;
curStr = cur == from ? fromStr : strs[cur];
} else {
cur_idx++;
}
if (cur==from && cur_idx == from_idx && started) return false;
cur_char = curStr.charAt(cur_idx);
started = true;
return true;
}
}
class NodeComp implements Comparator<Node> {
public int compare(Node n1, Node n2){
return n2.cur_char - n1.cur_char;
}
}
public String splitLoopedString(String[] strs) {
if (strs==null || strs.length==0) return null;
char maxChar = 'a';
int len = strs.length;
for (int i=0; i<strs.length; i++ ) {
for (char c : strs[i].toCharArray() ) {
if (c > maxChar ) maxChar = c;
String rev = reverse(strs[i]);
if ( rev.compareTo( strs[i] ) > 0) strs[i] = rev;
}
}
PriorityQueue<Node> queue = new PriorityQueue(1, new NodeComp());
for (int i=0; i<strs.length; i++ ) {
for (int j=0; j<strs[i].length(); j++) {
if (strs[i].charAt(j)== maxChar) {
queue.offer(new Node(strs, i, j, strs[i]));
queue.offer(new Node(strs, i, strs[i].length()-1-j, reverse(strs[i])));
}
}
}
StringBuilder ret = new StringBuilder();
while ( ! queue.isEmpty() ) {
PriorityQueue<Node> tempQueue = new PriorityQueue(1, new NodeComp());
char curChar = queue.peek().cur_char;
ret.append(curChar);
while (! queue.isEmpty() && curChar == queue.peek().cur_char ) {
Node curNode = queue.poll();
if (curNode.next()) tempQueue.offer(curNode);
}
queue = tempQueue;
}
return ret.toString();
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.