Saturday, September 12, 2015

Find lexicographically smallest and largest substring in O(n) time and O(1) space complexity

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