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);
}
}

List all zero sum sub arrays in the given array containing zero/positive/negative numbers

Problem:

Given an array containing negative/zero/positive elements.
Now list all the start and end positions of the sub arrays, whose sum is equal to zero.

For eg:
{2, -1, 0, 1, 1, -1, -2}

Output:
start=2, end=2
start=1, end=3
start=1, end=5
start=4, end=5
start=0, end=6

Algorithm:

maintain HashMap with key as current sum and value as a list of index positions
3 cases possible for every element:
1. current element is zero: output is: start=currentPosition, end=currentPosition
2. current sum is zero: output is: start=0, end=currentPosition
3. current sum is already present in the hashMap, which means that the sub array formed by positions "hashMap.get(currentSum)+1" and "currentPosition" sum is zero. so print all such possibilities with hashMap values

If the sum is not present in the hashMap, then insert (sum, {currentPosition})
if the sum is already present, then insert (sum, {previously inserted positions, currentPosition})

Program:

import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;

class PrintPositions {
static public void printPos(int[] in) {
Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();

int sum = 0;

for(int i=0; i<in.length; i++) {
sum = sum + in[i];

if(in[i] == 0)
System.out.println("start=" + i + ", end=" + i);
else if(sum == 0)
System.out.println("start=0, end=" + i);
else {
if(map.containsKey(sum)) {
List<Integer> positions = map.get(sum);

for(int pos : positions)
System.out.println("start=" + (pos+1) + ", end=" + i);
}
}

if(map.get(sum) == null) {
List<Integer> list = new ArrayList<Integer>();
list.add(i);
map.put(sum, list);
} else {
List<Integer> list = map.get(sum);
list.add(i);
}
}
}

static public void main(String[] args) {
PrintPositions pp = new PrintPositions();

pp.printPos(new int[]{2, -1, 0, 1, 1, -1, -2});
}
}

output:

start=2, end=2
start=1, end=3
start=1, end=5
start=4, end=5
start=0, end=6
start=1, end=7
start=4, end=7
start=6, end=7