# Simple O(N) solution based on prior frequency analysis

• ``````public class Solution {
//freq 1: g, u, w, x, z
//eight
//four
//two
//six
//zero

//freq 2: f, h, s
//five (four)
//three (eight)
//seven (six)

//freq 4: o, n
//one (zero, two, four)
//nine (one, seven), but note that 'n' appears twice in "nine"

public String originalDigits(String s) {
final char[] str = s.toCharArray();

final int[] paper = new int[10];

for(int i=0; i<str.length; i++) {
switch (str[i]) {
case 'g':
paper[8]++;
break;
case 'u':
paper[4]++;
break;
case 'w':
paper[2]++;
break;
case 'x':
paper[6]++;
break;
case 'z':
paper[0]++;
break;
case 'f':
paper[5]++;
break;
case 'h':
paper[3]++;
break;
case 's':
paper[7]++;
break;
case 'o':
paper[1]++;
break;
case 'n':
paper[9]++;
break;
default:
break;
}
}

paper[5] -= paper[4];
paper[3] -= paper[8];
paper[7] -= paper[6];

paper[1] -= paper[0] + paper[2] + paper[4];

paper[9] = (paper[9] - paper[1] - paper[7]) >> 1;

int sum = 0;
for(int i=0; i<10; i++) {
sum += paper[i];
}

final char[] ans = new char[sum];

for(int index = 0, i=0; i<10; i++) {
Arrays.fill(ans, index, (index += paper[i]), (char)(i + '0'));
}

return new String(ans);
}
}

``````

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