fork download
  1.  
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7.  
  8. class Ideone
  9. {
  10. public static void main (String[] args) throws java.lang.Exception
  11. {
  12. System.out.println(MNStringSolution.findPossibleSmallestNumberMatchingPattern("MNM"));
  13. }
  14. }
  15.  
  16.  
  17. class MNStringSolution {
  18. static PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
  19.  
  20. static int findPossibleSmallestNumberMatchingPattern(String pattern) {
  21. if (validatePattern(pattern))
  22. return -1;
  23. return Integer.parseInt(processString(pattern));
  24.  
  25. }
  26.  
  27.  
  28. private static boolean validatePattern(String pattern) {
  29. return (pattern.equals("") || pattern == "" || pattern == " " || pattern == null
  30. || getMNCount(pattern) != pattern.length());
  31. }
  32.  
  33. private static int getMNCount(String pattern) {
  34. int mCount = 0, nCount = 0;
  35. for (int i = 0; i < pattern.length(); i++) {
  36. if (pattern.charAt(i) == 'M') {
  37. mCount++;
  38. }
  39. if (pattern.charAt(i) == 'N') {
  40. nCount++;
  41. }
  42. }
  43. return nCount + mCount;
  44. }
  45.  
  46.  
  47. private static String processString(String input) {
  48. String res = "";
  49. int len = input.length();
  50. for (int k = 1; k <= len + 1; k++)
  51. heap.add(k);
  52. int mCount = 0;
  53. int nCount = 0;
  54. for (int i = 0; i < len; i++) {
  55. if (input.charAt(i) == 'M') {
  56. mCount = getConsecutiveCount(input, i, 'M');
  57. res += getElement(mCount + 1);
  58. mCount = 0;
  59. } else {
  60. res += getElement(1);
  61. nCount = 0;
  62. }
  63.  
  64. }
  65. return res + heap.poll();
  66. }
  67.  
  68. public static int getConsecutiveCount(String input, int index, char ch) {
  69. int c = 0;
  70. for (int i = index; i < input.length(); i++) {
  71. if (input.charAt(i) == ch) {
  72. c++;
  73. } else {
  74. break;
  75. }
  76. }
  77. return c;
  78.  
  79. }
  80.  
  81. private static String getElement(int k) {
  82. PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
  83. int tmp = 0, c = 0;
  84.  
  85. while (k-- > 0) {
  86. tmp = heap.poll();
  87. c++;
  88. if (k > 0) {
  89. pq.add(tmp);
  90. } else {
  91. break;
  92. }
  93. }
  94.  
  95. heap.addAll(pq);
  96. return tmp + "";
  97. }
  98.  
  99. }
Success #stdin #stdout 0.14s 57924KB
stdin
M
N
MM
MN
NM
NN
MMM
MMN
MNM
MNN
NMM
NMN
NNM
NNN
MMMM
MMMN
MMNM
MMNN
MNMM
MNMN
MNNM
MNNN
NMMM
NMMN
NMNM
NMNN
NNMM
NNMN
NNNM
NNNN
MMMMM
MMMMN
MMMNM
MMMNN
MMNMM
MMNMN
MMNNM
MMNNN
MNMMM
MNMMN
MNMNM
MNMNN
MNNMM
MNNMN
MNNNM
MNNNN
NMMMM
NMMMN
NMMNM
NMMNN
NMNMM
NMNMN
NMNNM
NMNNN
NNMMM
NNMMN
NNMNM
NNMNN
NNNMM
NNNMN
NNNNM
NNNNN
MMMMMM
MMMMMN
MMMMNM
MMMMNN
MMMNMM
MMMNMN
MMMNNM
MMMNNN
MMNMMM
MMNMMN
MMNMNM
MMNMNN
MMNNMM
MMNNMN
MMNNNM
MMNNNN
MNMMMM
MNMMMN
MNMMNM
MNMMNN
MNMNMM
MNMNMN
MNMNNM
MNMNNN
MNNMMM
MNNMMN
MNNMNM
MNNMNN
MNNNMM
MNNNMN
MNNNNM
MNNNNN
NMMMMM
NMMMMN
NMMMNM
NMMMNN
NMMNMM
NMMNMN
NMMNNM
NMMNNN
NMNMMM
NMNMMN
NMNMNM
NMNMNN
NMNNMM
NMNNMN
NMNNNM
NMNNNN
NNMMMM
NNMMMN
NNMMNM
NNMMNN
NNMNMM
NNMNMN
NNMNNM
NNMNNN
NNNMMM
NNNMMN
NNNMNM
NNNMNN
NNNNMM
NNNNMN
NNNNNM
NNNNNN
MMMMMMM
MMMMMMN
MMMMMNM
MMMMMNN
MMMMNMM
MMMMNMN
MMMMNNM
MMMMNNN
MMMNMMM
MMMNMMN
MMMNMNM
MMMNMNN
MMMNNMM
MMMNNMN
MMMNNNM
MMMNNNN
MMNMMMM
MMNMMMN
MMNMMNM
MMNMMNN
MMNMNMM
MMNMNMN
MMNMNNM
MMNMNNN
MMNNMMM
MMNNMMN
MMNNMNM
MMNNMNN
MMNNNMM
MMNNNMN
MMNNNNM
MMNNNNN
MNMMMMM
MNMMMMN
MNMMMNM
MNMMMNN
MNMMNMM
MNMMNMN
MNMMNNM
MNMMNNN
MNMNMMM
MNMNMMN
MNMNMNM
MNMNMNN
MNMNNMM
MNMNNMN
MNMNNNM
MNMNNNN
MNNMMMM
MNNMMMN
MNNMMNM
MNNMMNN
MNNMNMM
MNNMNMN
MNNMNNM
MNNMNNN
MNNNMMM
MNNNMMN
MNNNMNM
MNNNMNN
MNNNNMM
MNNNNMN
MNNNNNM
MNNNNNN
NMMMMMM
NMMMMMN
NMMMMNM
NMMMMNN
NMMMNMM
NMMMNMN
NMMMNNM
NMMMNNN
NMMNMMM
NMMNMMN
NMMNMNM
NMMNMNN
NMMNNMM
NMMNNMN
NMMNNNM
NMMNNNN
NMNMMMM
NMNMMMN
NMNMMNM
NMNMMNN
NMNMNMM
NMNMNMN
NMNMNNM
NMNMNNN
NMNNMMM
NMNNMMN
NMNNMNM
NMNNMNN
NMNNNMM
NMNNNMN
NMNNNNM
NMNNNNN
NNMMMMM
NNMMMMN
NNMMMNM
NNMMMNN
NNMMNMM
NNMMNMN
NNMMNNM
NNMMNNN
NNMNMMM
NNMNMMN
NNMNMNM
NNMNMNN
NNMNNMM
NNMNNMN
NNMNNNM
NNMNNNN
NNNMMMM
NNNMMMN
NNNMMNM
NNNMMNN
NNNMNMM
NNNMNMN
NNNMNNM
NNNMNNN
NNNNMMM
NNNNMMN
NNNNMNM
NNNNMNN
NNNNNMM
NNNNNMN
NNNNNNM
NNNNNNN
MMMMMMMM
MMMMMMMN
MMMMMMNM
MMMMMMNN
MMMMMNMM
MMMMMNMN
MMMMMNNM
MMMMMNNN
MMMMNMMM
MMMMNMMN
MMMMNMNM
MMMMNMNN
MMMMNNMM
MMMMNNMN
MMMMNNNM
MMMMNNNN
MMMNMMMM
MMMNMMMN
MMMNMMNM
MMMNMMNN
MMMNMNMM
MMMNMNMN
MMMNMNNM
MMMNMNNN
MMMNNMMM
MMMNNMMN
MMMNNMNM
MMMNNMNN
MMMNNNMM
MMMNNNMN
MMMNNNNM
MMMNNNNN
MMNMMMMM
MMNMMMMN
MMNMMMNM
MMNMMMNN
MMNMMNMM
MMNMMNMN
MMNMMNNM
MMNMMNNN
MMNMNMMM
MMNMNMMN
MMNMNMNM
MMNMNMNN
MMNMNNMM
MMNMNNMN
MMNMNNNM
MMNMNNNN
MMNNMMMM
MMNNMMMN
MMNNMMNM
MMNNMMNN
MMNNMNMM
MMNNMNMN
MMNNMNNM
MMNNMNNN
MMNNNMMM
MMNNNMMN
MMNNNMNM
MMNNNMNN
MMNNNNMM
MMNNNNMN
MMNNNNNM
MMNNNNNN
MNMMMMMM
MNMMMMMN
MNMMMMNM
MNMMMMNN
MNMMMNMM
MNMMMNMN
MNMMMNNM
MNMMMNNN
MNMMNMMM
MNMMNMMN
MNMMNMNM
MNMMNMNN
MNMMNNMM
MNMMNNMN
MNMMNNNM
MNMMNNNN
MNMNMMMM
MNMNMMMN
MNMNMMNM
MNMNMMNN
MNMNMNMM
MNMNMNMN
MNMNMNNM
MNMNMNNN
MNMNNMMM
MNMNNMMN
MNMNNMNM
MNMNNMNN
MNMNNNMM
MNMNNNMN
MNMNNNNM
MNMNNNNN
MNNMMMMM
MNNMMMMN
MNNMMMNM
MNNMMMNN
MNNMMNMM
MNNMMNMN
MNNMMNNM
MNNMMNNN
MNNMNMMM
MNNMNMMN
MNNMNMNM
MNNMNMNN
MNNMNNMM
MNNMNNMN
MNNMNNNM
MNNMNNNN
MNNNMMMM
MNNNMMMN
MNNNMMNM
MNNNMMNN
MNNNMNMM
MNNNMNMN
MNNNMNNM
MNNNMNNN
MNNNNMMM
MNNNNMMN
MNNNNMNM
MNNNNMNN
MNNNNNMM
MNNNNNMN
MNNNNNNM
MNNNNNNN
NMMMMMMM
NMMMMMMN
NMMMMMNM
NMMMMMNN
NMMMMNMM
NMMMMNMN
NMMMMNNM
NMMMMNNN
NMMMNMMM
NMMMNMMN
NMMMNMNM
NMMMNMNN
NMMMNNMM
NMMMNNMN
NMMMNNNM
NMMMNNNN
NMMNMMMM
NMMNMMMN
NMMNMMNM
NMMNMMNN
NMMNMNMM
NMMNMNMN
NMMNMNNM
NMMNMNNN
NMMNNMMM
NMMNNMMN
NMMNNMNM
NMMNNMNN
NMMNNNMM
NMMNNNMN
NMMNNNNM
NMMNNNNN
NMNMMMMM
NMNMMMMN
NMNMMMNM
NMNMMMNN
NMNMMNMM
NMNMMNMN
NMNMMNNM
NMNMMNNN
NMNMNMMM
NMNMNMMN
NMNMNMNM
NMNMNMNN
NMNMNNMM
NMNMNNMN
NMNMNNNM
NMNMNNNN
NMNNMMMM
NMNNMMMN
NMNNMMNM
NMNNMMNN
NMNNMNMM
NMNNMNMN
NMNNMNNM
NMNNMNNN
NMNNNMMM
NMNNNMMN
NMNNNMNM
NMNNNMNN
NMNNNNMM
NMNNNNMN
NMNNNNNM
NMNNNNNN
NNMMMMMM
NNMMMMMN
NNMMMMNM
NNMMMMNN
NNMMMNMM
NNMMMNMN
NNMMMNNM
NNMMMNNN
NNMMNMMM
NNMMNMMN
NNMMNMNM
NNMMNMNN
NNMMNNMM
NNMMNNMN
NNMMNNNM
NNMMNNNN
NNMNMMMM
NNMNMMMN
NNMNMMNM
NNMNMMNN
NNMNMNMM
NNMNMNMN
NNMNMNNM
NNMNMNNN
NNMNNMMM
NNMNNMMN
NNMNNMNM
NNMNNMNN
NNMNNNMM
NNMNNNMN
NNMNNNNM
NNMNNNNN
NNNMMMMM
NNNMMMMN
NNNMMMNM
NNNMMMNN
NNNMMNMM
NNNMMNMN
NNNMMNNM
NNNMMNNN
NNNMNMMM
NNNMNMMN
NNNMNMNM
NNNMNMNN
NNNMNNMM
NNNMNNMN
NNNMNNNM
NNNMNNNN
NNNNMMMM
NNNNMMMN
NNNNMMNM
NNNNMMNN
NNNNMNMM
NNNNMNMN
NNNNMNNM
NNNNMNNN
NNNNNMMM
NNNNNMMN
NNNNNMNM
NNNNNMNN
NNNNNNMM
NNNNNNMN
NNNNNNNM
NNNNNNNN
stdout
2143