def licenseKeyFormatting(self, S, K):
:type S: str
:type K: int
count = 0
S = S.replace('-','')
for i in reversed(S): # returns an iterator
count += 1
if count % K == 0 and count < len(S):
How come string.replace() runs faster than looping over and checking for "-" directly? This runs faster than the native loop, non-striped solution. Isn't string.replace() using regex under the hood, hence should be slower?
Here's one that avoids both string split which creates extra memory for string array and StringBuilder insert which is an O(n) operation. The trick to single pass is to work backwards, which does require a reverse at the end of the routine.
public string LicenseKeyFormatting(string S, int K)
StringBuilder sb = new StringBuilder();
int charLen = 0;
for (int i = S.Length - 1; i >= 0; i--)
if (S[i] != '-')
if (charLen > 0 && charLen % K == 0)
char chars = sb.ToString().ToCharArray();
return new string(chars);
Yes I thought that the [::-1] might also be O(n) but that it would at least be a very fast iteration as it did nothing to each element. In any case, the key is that replace and upper are written in C. Thanks.