题目
给出一个字符串作为输入，找出其中最长的连续数字串并返回其长度和起始index。如果存在长度相同的连续数字串，返回最后一个连续数字串。如果没有，返回0和0。
Analysis
对于这道题目，首先我们需要进一步缩小题目范围。题目中并没有给出字符串中的数字都是什么数字。比如是否包含负数，是否包含小数等。因此简单起见，我们假设该输入字符串中只包含正整数。且假设输入字符串中没有空格。
设输入字符串的长度为n。
从Best Conceivable Time的角度考虑，这道题的时间复杂度至少为O(n)。也就是说，对于这道题而言，我们至少需要遍历整个输入的字符串一次才能得出答案。因此在时间复杂度角度考虑，我们并没有多少优化的空间。
从空间复杂度的角度考虑，brute-force解法比较直观，就是遍历一遍整个输入字符串，找出并记录其中所有的连续数字子串。然后在所有被记录的数字子串中找出最长的那个。因为题目要求有多个最长子串时返回最后一个，所以我们只需要返回最后一个被记录的最长子串即可。这个方法最坏情况下需要记录整个输入字符串。所以空间复杂度为O(n)。
具体实现如下：
public class LongestNumberSubstring {
public static int[] findLongestNumSubstring(String input) {
// If the string is empty, return [0, 0] directly.
if (input == null || input.length() == 0) {
return new int[]{0, 0};
}
int index = 0;
int[] ret = new int[]{0, 0}; //[start_index, length]
while (index < input.length()) {
StringBuilder sb = new StringBuilder();
while (index < input.length() && Character.isDigit(input.charAt(index))) {
sb.append(input.charAt(index));
index++;
}
// If current substring is not empty and is longer than or equal to the previously found substring
// Put it in return values.
if (sb.length() != 0 && ret[1] <= sb.length()) {
ret[1] = sb.length();
ret[0] = index - sb.length();
}
index++;
}
return ret;
}
优化
但事实上，考虑到我们需要的只是子字符串的起始index和长度，这道题可以用2 pointers的方法解决。并不需要记录中间产生的任何子字符串。这样的话我们可以将算法的空间复杂度降到O(1)。
具体算法为：从头到尾遍历字符串，每当遇到数字连续数字子串时，记录其长度。并与全局记录的最长长度相比较。如果更长的话，就记录当前长度和开始index。
实现如下：
public class LongestNumberSubstring {
public static int[] findLongestNumSubstring(String input) {
// If the string is empty, return [0, 0] directly.
if (input == null || input.length() == 0) {
return new int[]{0, 0};
}
int index = 0;
int[] ret = new int[]{0, 0}; //[start_index, length]
int currLen = 0;
while (index < input.length()) {
currLen = 0;
while (index < input.length() && Character.isDigit(input.charAt(index))) {
currLen++;
index++;
}
// If current substring is longer than or equal to the previously found substring
// Put it in return values.
if (currLen != 0 && ret[1] <= currLen) {
ret[1] = currLen;
ret[0] = index - currLen;
}
index++;
}
return ret;
}
}
