package com.interview.number;

/**
 * You are given an array of n elements [1,2,....n]. For example {3,2,1,6,7,4,5}.
Now we create a signature of this array by comparing every consecutive pair of elements.
If they increase, write I else write D. For example for the above array, 
the signature would be "DDIIDI". The signature thus has a length of N-1. Now the question is given a signature, 
compute the lexicographically smallest permutation of [1,2,....n]. 
Write the below function in language of your choice.
 */
public class GenerateSignature {

    /**
     * Idea is first to get long increasing subsequence sum using kadane. Then see if we have enough
     * I before longest kadane sequence. If yes then we can start filling with 1 else use kadane - I's count to start
     * the increasing sequence.
     * @param input
     * @return
     */
    public int[] generate(char input[]){
        Pair p = kadane(input);
        int result[] = new int[input.length+1];
        if(p.start == -1){
            fillResult(input,result,1);
            return result;
        }
        int count = 0;
        for(int i = 0; i < p.start; i++){
            if(input[i] == 'I'){
                count++;
            }else{
                count--;
            }
        }
        fillResult(input,result,count < p.size ? p.size - count +1 : 1);
        return result;
        
    }
    
    private void fillResult(char input[],int result[], int start){
        result[0] = start;
        for(int i=0 ; i < input.length; i++){
            if(input[i] == 'D'){
                result[i+1] = result[i] -1;
            }else{
                result[i+1] = result[i] + 1;
            }
        }
    }
    
    class Pair{
        int start;
        int size;
    }
    
    private Pair kadane(char input[]){
        int max = -1;
        int index = 0;
        int val = 0;
        int sum = 0;
        for(int i =0; i < input.length; i++){
            val = input[i] == 'D' ? 1 : -1;
            sum += val;
            if(sum <= 0){
                sum = 0;
                index = i+1;
                continue;
            }
            if(max < sum){
                max = sum;
            }
        }
        Pair p = new Pair();
        p.size = max;
        p.start = index;
        return p;
    }
    
    //https://learn.hackerearth.com/forum/182/lexicographically-smallest-permutation-given-a-signature/
    //Alternative O(n) approach
    int[] generate2(char[] input) {
        int n = input.length+1;
        int[] result = new int[n];
        int i;
        for (i = 0; i < n; i++) {
            result[i] = i+1;
        }
        i = 0;
        while(i < n-1) {
            int start = -1, end = -1;
            while(i < n-1 && input[i] == 'D') {
                if(start == -1) start = i;
                end = i;
                i++;
            }
            if(start!=-1) reverse(result, start, end+1);
            i++;
        }
        return result;
    }

    void reverse(int[] result, int start, int end) {

        while(start < end) {
            int tmp = result[start];
            result[start] = result[end];
            result[end] = tmp;
            start++;
            end--;
        }
    }
    
    //End of alternative approach
    
    public static void main(String args[]){
        String input = "IIIDIIDDDDIIDDD";
        GenerateSignature gs = new GenerateSignature();
        int result[] = gs.generate(input.toCharArray());
        for(int i=0; i < result.length; i++){
            System.out.print(result[i] + " ");
        }
    }
}

@@ -109,17 +109,17 @@
 ,7,4,5%7D.
-%0A
+ 
 Now we c
@@ -143,16 +143,19 @@
  of this
+%0A *
  array b
@@ -185,17 +185,16 @@
 cutive p
-a
 ir of el
@@ -200,17 +200,17 @@
 lements.
-%0A
+ 
 If they 
@@ -240,16 +240,19 @@
 write D.
+%0A *
  For exa
@@ -277,17 +277,16 @@
  array, 
-%0A
 the sign
@@ -349,16 +349,19 @@
  of N-1.
+%0A *
  Now the
@@ -392,17 +392,16 @@
 nature, 
-%0A
 compute 
@@ -462,1864 +462,77 @@
 .n%5D.
- %0AWrite the below function in language of your choice.%0A */%0Apublic class GenerateSignature %7B%0A%0A    /**%0A     * Idea is first to get long increasing subsequence sum using kadane. Then see if we have enough%0A     * I before longest kadane sequence. If yes then we can start filling with 1 else use kadane - I's count to start%0A     * the increasing sequence.%0A     * @param input%0A     * @return%0A     */%0A    public int%5B%5D generate(char input%5B%5D)%7B%0A        Pair p = kadane(input);%0A        int result%5B%5D = new int%5Binput.length+1%5D;%0A        if(p.start == -1)%7B%0A            fillResult(input,result,1);%0A            return result;%0A        %7D%0A        int count = 0;%0A        for(int i = 0; i %3C p.start; i++)%7B%0A            if(input%5Bi%5D == 'I')%7B%0A                count++;%0A            %7Delse%7B%0A                count--;%0A            %7D%0A        %7D%0A        fillResult(input,result,count %3C p.size ? p.size - count +1 : 
+%0A *%0A * Time complexity O(n)%0A * Space complexity O(
 1)
-;
 %0A 
-       return result;%0A        %0A    %7D%0A    %0A    private void fillResult(char input%5B%5D,int result%5B%5D, int start)%7B%0A        result%5B0%5D = start;%0A        for(int i=0 ; i %3C input.length; i++)%7B%0A            if(input%5Bi%5D == 'D')%7B%0A                result%5Bi+1%5D = result%5Bi%5D -1;%0A            %7Delse%7B%0A                result%5Bi+1%5D = result%5Bi%5D + 1;%0A            %7D%0A        %7D%0A    %7D%0A    %0A    class Pair%7B%0A        int start;%0A        int size;%0A    %7D%0A    %0A    private Pair kadane(char input%5B%5D)%7B%0A        int max = -1;%0A        int index = 0;%0A        int val = 0;%0A        int sum = 0;%0A        for(int i =0; i %3C input.length; i++)%7B%0A            val = input%5Bi%5D == 'D' ? 1 : -1;%0A            sum += val;%0A            if(sum %3C= 0)%7B%0A                sum = 0;%0A                index = i+1;%0A                continue;%0A            %7D%0A            if(max %3C sum)%7B%0A                max = sum;%0A            %7D%0A        %7D%0A        Pair p = new Pair();%0A        p.size = max;%0A        p.start = index;%0A        return p;%0A    %7D%0A    %0A    //
+*%0A * Reference 
 http
@@ -630,42 +630,55 @@
 e/%0A 
-   //Alt
+*/%0Apublic class Gen
 er
-n
 at
-ive O(n) approach%0A   
+eSignature %7B%0A%0A    public
  int
@@ -688,17 +688,16 @@
 generate
-2
 (char%5B%5D 
@@ -1022,18 +1022,58 @@
 -1) 
-start = i;
+%7B%0A                    start = i;%0A                %7D
 %0A   
@@ -1153,13 +1153,33 @@
 tart
+ 
 !=
+ 
 -1)
+ %7B%0A               
  rev
@@ -1206,16 +1206,30 @@
 end+1);%0A
+            %7D%0A
         
@@ -1281,16 +1281,24 @@
  %7D%0A%0A    
+private 
 void rev
@@ -1542,47 +1542,8 @@
    %0A
-    //End of alternative approach%0A    %0A
     

update generate signature logic