Java String Compare

Problem
Given a string, find out the lexicographically smallest and largest substring of length .

[Note: Lexicographic order is also known as alphabetic order dictionary order. So “ball” is smaller than “cat”, “dog” is smaller than “dorm”. Capital letter always comes before smaller letter, so “Happy” is smaller than “happy” and “Zoo” is smaller than “ball”.]

Input Format

First line will consist a string containing english alphabets which has at most characters. 2nd line will consist an integer .

Output Format

In the first line print the lexicographically minimum substring. In the second line print the lexicographically maximum substring.

Sample Input

1
2
welcometojava
3

Sample Output

1
2
ava
wel

Explanation

Here is the list of all substrings of length :

1
2
3
4
5
6
7
8
9
10
11
wel
elc
lco
com
ome
met
eto
toj
oja
jav
ava

Among them ava is the smallest and wel is the largest.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/**
 * Copyright 2016. ABN Software. All Rights reserved.<br>
 * <br>
 * Created ..... 3 окт. 2016 г.<br>
 * <br>
 */

package info.abnsoft.java.HackerRank.sep2016;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

/**
 * @author annik
 *
 */

public class SolutionStringLexi {

    public static void main( String[] args ) {

        /*
         * Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named
         * Solution.
         */

        Scanner sc = new Scanner( System.in );
        String str = sc.nextLine();
        int count = sc.nextInt();
        sc.close();
//        System.out.println(str);
//        System.out.println(count);
        // splitted words :
        List<String> splitted = new ArrayList<String>();
        // sorted words
        List<String> result = new LinkedList<String>();
        if ( str.length() <= count ) {
            result.add( str );
        } else {
            for (int i = 0; i <= str.length() - count; i++) {
                //            System.out.println(str.substring(i,i+count));
                splitted.add( str.substring( i, i + count ) );
            }
            String cur = splitted.get( 0 );
            result.add( cur ); // add 1st element

            System.out.println( splitted );

            // TODO : if size==0 ?
            for (int i = 1; i < splitted.size(); i++) {
                boolean notFoundMin = true;
                for (int j = 0; j < result.size(); j++) {
                    cur = result.get( j );
                    if ( isLexicSmaller( splitted.get( i ), cur ) ) {
                        // when arr[i] is smaller insert at first
                        result.add( j, splitted.get( i ) );
                        notFoundMin = false;
//                        cur = splitted.get( i );
                        break;
                    }
                }
                if ( notFoundMin ) {
                    result.add( splitted.get( i ) ); // add at the end of list
//                    cur = splitted.get( i );
                }
            }
        }
        System.out.println( result );
        System.out.println( ( (LinkedList<String>) result ).getFirst() );
        System.out.println( ( (LinkedList<String>) result ).getLast() );
    }

    /*
     * When a < b returns true, else FALSE.
     */

    private static boolean isLexicSmaller( String a, String b ) {

        boolean result = false;
        int i = -1;
        do {
            i++;
            if ( a.charAt( i ) != b.charAt( i ) ) {
                if ( a.charAt( i ) < b.charAt( i ) ) {
                    result = true;
                }
            }
        } while (a.charAt( i ) == b.charAt( i ) && i < ( a.length() - 1 ));
        return result;
    }

}
Tagged , , , . Bookmark the permalink.

Leave a Reply