Amazon Interview Question
Software Engineer in Testspublic class NumSubString {
public static int numSubString(String subStr, String inputStr) {
if(subStr.length() == 0) return 0;
String newStr = inputStr.replaceAll(subStr, "");
return (inputStr.length() - newStr.length())/subStr.length();
}
public static void main(String[] args) {
System.out.println(NumSubString.numSubString("bc", "abcabcxbcabc"));
System.out.println(NumSubString.numSubString("abc", "abcabcxbcabcbc"));
}
}
Using Java String's replaceAll method to get rid of the subStr. That is replace all occurrences of the given substr with an empty string. Then, simply calculate the difference between the length of the input string and the newly formed string. This difference when divided by the substr's length gives us the number of occurrences of the given substr.
suffix trees and keep count
- Anonymous April 28, 2011