Given a string and an integer k.
a) find the lexicographically smallest substring of length k in the given String.
b) find the lexicographically largest substring of length k in the given String.
eg: String="welcometojava", k=3
now all possible substrings of length 3 are: wel, elc, lco, com, ome, met, oja, jav, ava
wrt dictionary, the first occuring substring is: "ava" and the last is "wel"
Code:
class LexicoString {
static public void printLex(String str, int k) {
int[] chars = new int[str.length()];
for(int i=0; i<str.length(); i++)
chars[i] = (int) str.charAt(i);
int minSum = 0, minPos = -1, maxSum = 0, maxPos = -1;
int sum = 0;
int multiplier = 1;
for(int i=k-1; i>=0; i--) {
sum = sum + chars[i]*multiplier;
minSum = minSum + 122 * multiplier;
multiplier = multiplier * 10;
}
multiplier = multiplier/10;
for(int i=0; i<chars.length-k+1; i++) {
if(i != 0) {
sum = sum - (chars[i-1] * multiplier);
sum = sum * 10;
sum = sum + chars[i+k-1];
}
System.out.println("i=" + i + ", substring=" + str.substring(i, i+k) + ", sum=" + sum);
if(sum < minSum) {
minSum = sum;
minPos = i;
}
if(sum > maxSum) {
maxSum = sum;
maxPos = i;
}
}
System.out.println("Positions: min=" + minPos + ", max=" + maxPos);
}
static public void main(String[] args) {
printLex("welcometojava", 3);
}
}
No comments:
Post a Comment