CareerCup

Algo:
step 1: Convert this string to list of the substrings of size x
step 2: sort individual substring characters make things better use only unique characters from each substring so that duplicate number generation can be avoided
step 3: generate n th string from all these substrings, i.e. generate N the set in the cartesian product of these substring characters.

package com.practice.algo;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;

public class KthNumberInSorted {

  private static List<Integer> getNthNumber(List<List<Integer>> lists, int n) {
    int lSize = lists.size();
    int[] mul = new int[lSize];
    mul[lSize - 1] = 1;
    for (int i = lSize - 2; i >= 0; i--) {
      mul[i] = mul[i + 1] * lists.get(i + 1).size();
    }
    List<Integer> l = new ArrayList<>();
    n -= 1;
    for (int i = 0; i < lSize; i++) {
      int r = n / mul[i];
      n = n - r * mul[i];
      l.add(lists.get(i).get(r));
    }
    return l;
  }

  private static String getNthNumber(String s, int x, int k) {
    List<Integer> l = new ArrayList<>();
    for (int i = 0; i < s.length(); i++) {
      l.add(s.charAt(i) - '0');
    }
    List<List<Integer>> listOfLists = new ArrayList<>();
    int start = 0;
    while (start < s.length()) {
      int end = Math.min(s.length(), start + x);
      // make it unique
      List<Integer> list = new ArrayList<>(new HashSet<>(l.subList(start, end)));
      Collections.sort(list);
      listOfLists.add(list);
      start = end;
    }
    StringBuilder stringBuilder = new StringBuilder();
    for (Integer i : getNthNumber(listOfLists, k)) {
      stringBuilder.append(i);
    }
    return stringBuilder.toString();
  }

  public static void main(String[] args) {
    System.out.println(getNthNumber("1234567891", 5, 3));
    System.out.println(getNthNumber("123456789", 3, 3));
  }

}