CareerCup

Can you explain why your example "987"->"1023" violate the rule 3?

Assume:
"input=987, return=1023" is a wrong example, which violates the rule 3.

A brute-force algorithms:
Define Two Helper Data Array:
MAX_Data_Helper = { 0, 9, 89, 789, 6789, 56789, 456789, 3456789, 23456789, 123456789 };
MIN_Data_Helper = { 0, 12, 123, 1234, 12345, 123456, 1234567, 12345678, 123456789, -1 };

Algorithm is shown below: Given a number: n
Case 1: If n is negative, return 0;
Case 2: If n is >= 123456789, then there is no solution;
Case 3: Otherwise, n is in [0, 123456789) [for example: n = 321]
3.1: Find the minimum upper bound in MAX_Data_Helper. [It is 789]
3.2: If n < 123, then return 123. [gets 123 from MAX_Data_Helper]
Otherwise, brute-check all numbers from n+1 to minimum upper bound. [In this case, check from 322 to 789]
3.3: the three rules in together means (lower sinificant degit > higher sinificant degit).

Performance Analysis:
Ignore negative numbers and very large numbers > 123456789.
Assume numbers are uniformly random in [0, 123456789).
Then, most numbers get Big-O: O(1). For example, for numbers in [56789, 123456), return 123456 immediately.
As n goes larger, the precentage of numbers with O(1) is larger. So, the amortized cost is O(1).
But the worst case performance is very bad. for example, if n = 23456789, it is costly to find the next.

private static int getInteger(int input)
{
int rem1;
int rem2;
boolean found = false;
HashSet<Integer> set;

if(input < 0)
{
return 0;
}
else if(input/10 == 0)
{
return input+1;
}
else
{
while(!found)
{
found = true;
int temp = input;
set = new HashSet<Integer>();
rem1 = -1;
rem2 = -1;
System.out.println("INPUT: "+temp);
while(temp != 0)
{
rem1 = temp % 10;
temp = temp / 10;

if(!set.add(rem1) || (rem2 != -1 && rem2 < rem1))
{
found = false;
break;
}
rem2 = rem1;
}

if(found)
{
break;
}
else
{
input++;

}
}

return input;
}
}

The following code works fine, tested:

private static int getInteger(int input)
{
int rem1;
int rem2;
boolean found = false;
HashSet<Integer> set;

if(input < 0)
{
return 0;
}
else if(input/10 == 0)
{
return input+1;
}
else
{
while(!found)
{
found = true;
int temp = input;
set = new HashSet<Integer>();
rem1 = -1;
rem2 = -1;
System.out.println("INPUT: "+temp);
while(temp != 0)
{
rem1 = temp % 10;
temp = temp / 10;

if(!set.add(rem1) || (rem2 != -1 && rem2 < rem1))
{
found = false;
break;
}
rem2 = rem1;
}

if(found)
{
break;
}
else
{
input++;

}
}

return input;
}
}

Assuming input is a positive integer, following is code in C++:

bool nextInteger(string& res, int i, const string& src, bool used[], bool alreadyLarger)
{
	if(i == src.size()) return src < res;
	if(alreadyLarger){//set every position left with smallest integer not used
		int k = 0;
		for(; i < src.size(); ++i){
			for(; k < 10; ++k){
				if(!used[k]){
					res[i] = '0' + k++;
					break;
				}
			}
		}
		return true;
	}
	
	for(char c = src[i]; c <= '9'; ++c){
		if(used[c - '0']) continue;
                res[i] = c;
		used[c - '0'] = true;
		if(nextInteger(res, i + 1, src, used, c > src[i])) return true;
		used[c - '0'] = false;
	}
	return false;
}
string nextInteger(const string& input)
{
	static const string limit[11] = {
		"",
		"9",
		"98",
		"987",
		"9876",
		"98765",
		"987654",
		"9876543",
		"98765432",
		"987654321",
		"9876543210",
	};

	int len = input.size();
	if(len > 10 || len == 10 && limit[10] <= input) return "";//no such number

	string res;
	if(limit[len] <= input){//result is smallest with length = input.length + 1
		res.resize(len + 1);
		res[0] = '1';
		res[1] = '0';
		for(int i = 2; i <= len; ++i){
			res[i] = i + '0';
		}
	}
	else{//get next larger with length = input.length
		res.resize(len);
		bool used[10] = {0};
		nextInteger(res, 0, input, used, false);
	}
	return res;
}

Any input with > 10 characters will definitely have a repeated character - why? (pigeon hole principle)
Any input with 10 characters also will not have a valid solution - why? because for 10 characters we need to include 0-9, in increasing order which means 0 has to be at the beginning which makes it a 9 digit integer.
Any input with 9 digits can have 2 different solutions:
if input is < 123456789 then answer is 123456789
else no solution
similarly we can solve other cases - should be trivial.

public class IncrementString {

	public static String nextString(String num) {
		char[] numArr = num.toCharArray();

		boolean canBeIncrementedWithinTheSameNumberOfDigit = true;

		for (int i = 0; i < numArr.length; i++) {

			if ((10 - (numArr[i] - '0')) < (numArr.length - 1 - i)) {
				canBeIncrementedWithinTheSameNumberOfDigit = false;
				break;
			}

		}

		if (canBeIncrementedWithinTheSameNumberOfDigit) {

			for (int i = 0; i < numArr.length; i++) {
				numArr[i] = ++numArr[i];
			}
			return new String(numArr);

		} else {
			char[] newNumArr = new char[numArr.length + 1];
			for (int i = 0; i <= numArr.length; i++) {
				newNumArr[i] = (char) ('0' + (i + 1));
			}

			return new String(newNumArr);
		}

	}

	public static void main(String[] args) {
		System.out.println(nextString("978"));
	}
}

Unless I'm missing something, I also agree that 1023 seems to violate the rule requiring an incremental sequence of numbers. If that's true, then it seems to me that the entire set of valid numbers would be (in their string representation) sub-strings of either of the following:

"9876543210"
"123456789"

That means there are only 100 valid numbers: sum(i=1...9: i) + sum(j=1...10: j) = (9*9 + 9)/2 + (10*10 + 10)/2 = 45 + 55 = 100. That means they can all easily fit into memory of any reasonable device today and calculating them all should be fast as well. Store the calculated values in a map of seq_i -> seq_(i+1) and lookup will be trivial. Brute force, I know, but it seems like a reasonable trade off for O(1) evaluation. If something more general is required, it is still possible to generate the subset of possible numbers based off of the position in the string. However, as I was trying that approach, it just seemed like there was way too many logic forks.

import com.google.common.collect.Lists;
import com.google.common.collect.Maps;

import java.util.Collections;
import java.util.List;
import java.util.Map;

class GoogleIntSequence {
    private static final String seq =    "123456789";
    private static final String revSeq = "9876543210";
    private static Map<String, String> nextMap;

    static {
        nextMap = Maps.newHashMap();
        List<Long> allVals = Lists.newArrayList();
        for (int i = 0; i < revSeq.length(); ++i) {
            for (int j = i+1; j <= revSeq.length(); ++j) {
                if (j <= seq.length()) {
                    allVals.add(Long.parseLong(seq.substring(i, j)));
                }
                allVals.add(Long.parseLong(revSeq.substring(i, j)));
            }
        }

        Collections.sort(allVals);
        for (int i = 0; i < allVals.size() - 1; ++i) {
            nextMap.put(allVals.get(i).toString(), allVals.get(i+1).toString());
        }
    }

    public static String findNextSequence(String s) {
        if ("9876543210".equals(s)) {
            throw new IllegalArgumentException("Last valid number input");
        }
	
        if (!nextMap.containsKey(s)) {
            throw new IllegalArgumentException("Input integer not well formed.");
        }

        return nextMap.get(s);
    }
}

Best approach in my opinion is (assuming the number can't be more than 10^10):

Add the following numbers into a sorted list, prefixing a particular sequence,
1
12
123
...
123456789

Then start with 2:
2
23
234
2345
...
2345678901

so on

Finally, do a binary search on the sorted array and find the next biggest element.

#include <iostream>
#include <stdlib.h>

bool nodup_digit(int x)
{
  int a[10] = {0};

  while (x > 0)
  {
    int d = x % 10;
    a[d] = a[d] + 1;
    if (a[d] > 1)
      return false;
    x /= 10;
  }

  return true;
}

bool increment(int x)
{
  int max = 9;

  while (x > 0)
  {
    int d = x % 10;
    if (d > max)
      return false;

    max = d;
    x /= 10;
  }

  return true;
}

int next(int n)
{
  if (n < 0)
    return 1;

  ++n;

  while (!nodup_digit(n) || !increment(n))
  {
    ++n;
  }

  return n;
}

int main(int argc, char* argv[])
{
  int x = atoi(argv[1]);
  std::cout << next(x) << "\n";
  return 0;
}

assuming the maximum we can get is '123456789', so it's invalid for input bigger than '123456788'
then we plus the input by 1, so we can check our generated result by greater or equal function.
first we generate the biggest valid number we could have for the length of input, e.g 899 as input, the biggest is 789
if it's smaller than input+1, simply return 1234, as we know it's the smallest valid result.
if for input 688, the maximum 789 is bigger than it, so we scrimp it from the highest bit.

time complexity is (n^2) which n is the length of input string, space complexity is n.

#include <vector>

template<typename T>
bool _ge(const T &str_1, const string &str_2) {
  if (str_1.size() > str_2.size()) return true;
  if (str_1.size() < str_2.size()) return false;
  if (str_1.size() == str_2.size()) {
    for (int i = 0; i < str_1.size(); ++i) {
      if (str_1[i] < str_2[i]) return false;
      if (str_1[i] > str_2[i]) return true;
    }
  }
  return true;
}

string* nextInteger(const string& input_0) {
  // valid input should not greater than 123456788
  if (!_ge(string("123456788"), input_0)) return NULL;
  // plus the input by one
  string input(input_0);
  for (int i = input.size() - 1; i >= 0; --i) {
    if (input[i] == '9') {
      input[i] = '0';
      if (i == 0) {
        input = "1" + input;
      }
    } else {
      input[i] += 1;
      break;
    }
  }
    
  vector<char> buffer;
  // construct a string of the maximum for the same length.
  for (int i = input.size() - 1; i >= 0; --i) {
    buffer.push_back('9' - i);
  }
  // the next greater one needs extra significant bit.
  if (!_ge(buffer, input)) {
    string *next = new string(input.size() + 1, '0');
    for (int i = 0; i <= input.size(); ++i) {
      (*next)[i] += i + 1;
    }
    return next;
  }
  // the next greater one doesn't need extra significant bit.
  char prev = input[0];
  int i = 0;
  for (; i < input.size(); ++i) {
    // choose the bigger one, the previous bit + 1 or the input bit.
    buffer[i] = prev > input[i]? prev: input[i];
    if (!_ge(buffer, input)) {
      // if we found the current number is lower than the input one, increase
      // current bit by 1
      buffer[i] += 1;
      ++i;
      break;
    }
    prev = buffer[i] + 1;
  }
  for (; i < input.size(); ++i) {
    // since previous bit has been increased by 1, the smaller one for the rest
    // bits will just increase 1 each.
    buffer[i] = buffer[i - 1] + 1;
  }
  string *next = new string(buffer.size(), '0');
  for (int i = 0; i < buffer.size(); ++i) (*next)[i] = buffer[i];
  return next;
}

I think this covers all cases. =)

public int nextInteger(String input) {
		int in = Integer.parseInt(input);
		String nums = "123456789"; // will be used as a sliding substring window
		int length = input.length();
		// find the corresponding index in nums from first character of input.
		int firstCharIndex = Integer.parseInt(input.charAt(0) + "") - 1; 
		int lastCharIndex = firstCharIndex + (length - 1); // expected last index of the sliding window
		int i = 0;
		int j = length - 1;
		
		// invalid if 9 or more digits
		if(length >= 9)
			return -1;
		
		if(in <= 0)
			return 1;
		
		// overflow to next digit if the expected last index constructed is greater nums' length
		if(lastCharIndex > nums.length() - 1) {
			j = length;
			return Integer.parseInt(nums.substring(i, j + 1));
		}
		
		// compare the input with a sliding window of nums of the same length.
		while(j < nums.length()) {
			int checkNum = Integer.parseInt(nums.substring(i, j + 1));
			// return when sliding window is larger than the input
			if(checkNum > in)
				return checkNum;
			
			i++;
			j++;
		}
		
		return -1;
		
	}

public class NextAscendingPositive {

	public static String nextInteger(String num){
		int n = num.length();
		if(n <= 0 || n >= 9) return null;

		int prev = 0;
		int i;
		for(i = 0; i < n; i++){
			int digit = num.charAt(i) - '0';
			// check blocker

			if(digit <= prev){
				return num.substring(0,i)+createSequence(prev+1, n-i);
			}

			if(digit + n-i-1 > 9) {
				break;
			}

			prev = digit;		
		}

		String ret = null;
		if(i >= n){ // blocker not found
			ret = createSequence((int)(num.charAt(0)-'0'+1), n);
			if(ret == null) {
				ret =  createSequence(1, n+1);
			}
		} else {
			for(i = i-1; i >=0; i--){
				int digit = num.charAt(i) - '0'+1;
				if(digit + n-i-1 <= 9)  {
					ret = num.substring(0,i)+createSequence(digit, n-i);
					break;
				}	
			}
			if(ret  == null){
				ret = createSequence(1, n+1);
			}

		}

		return ret;
	}


	private static String createSequence(int startDigit, int nDigs){
		if(startDigit+nDigs > 10) return null;
		StringBuilder sb = new StringBuilder();
		for(int  i = 0; i < nDigs; i++){
			sb.append(startDigit++);
		}
		return sb.toString();
	}

	
	public static void main(String[] args) {
		int num = 34234;
		test(num);
		test(12345);
		test(93245);
		test(985);
		test(67234);
		test(6723);
		test(123458769);
		
	}


	private static void test(int num) {
		System.out.println("Next of '"+ num+ "' is " + nextInteger(String.valueOf(num)) );
	}
	
}

package google;

import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class NextIntWithUniqueDigits {
    @Test
    public void test() {
        assertEquals("1", nextInt("0"));
        assertEquals("124", nextInt("000123"));
        assertEquals("124", nextInt("123"));
        assertEquals("134", nextInt("132"));
        assertEquals("234", nextInt("191"));
        assertEquals("345", nextInt("298"));
        assertEquals("1234", nextInt("987"));
        assertEquals("1234", nextInt("789"));
        assertEquals("1567", nextInt("1543"));
        assertEquals("45678", nextInt("41543"));
    }

    @Test(expected = IllegalArgumentException.class)
    public void testBig() {
        nextInt("123456789");
    }

    @Test(expected = IllegalArgumentException.class)
    public void testEmpty() {
        nextInt("");
    }

    public static String nextInt(String previous) {
        if (!previous.matches("\\d+")) {
            throw new IllegalArgumentException("Argument should contain at least one digit and no other characters.");
        }

        previous = trimLeadingZeros(previous);

        if (previous.equals("0")) {
            return "1";
        }
        if (previous.length() > 9 || Integer.valueOf(previous) >= 123456789) {
            throw new IllegalArgumentException(String.format("No next integer available for %s.", previous));
        }

        char[] chs = new char[previous.length() + 1];
        chs[0] = '0';
        System.arraycopy(previous.toCharArray(), 0, chs, 1, previous.length());

        modifyToNextInt(chs);

        if (chs[0] == '0') {
            return new String(chs, 1, chs.length - 1);
        } else {
            return new String(chs);
        }
    }

    private static String trimLeadingZeros(String str) {
        int nonLeadingZeroChar = 0;
        while (str.charAt(nonLeadingZeroChar) == '0' && nonLeadingZeroChar != str.length() - 1) {
            nonLeadingZeroChar++;
        }
        if (nonLeadingZeroChar > 0) {
            return str.substring(nonLeadingZeroChar);
        } else {
            return str;
        }
    }

    private static int findDigitLessThenPrevious(char[] chs) {
        int idx = 1;
        while (idx < chs.length - 1 && chs[idx] > chs[idx - 1]) {
            idx++;
        }
        return idx;
    }

    private static int findDigitToChangeFrom(char[] chs) {
        int idx = findDigitLessThenPrevious(chs);
        while (idx > 0 && ('9' - (Math.max(chs[idx], chs[idx - 1]) + 1)) < chs.length - idx) {
            idx--;
        }
        return idx;
    }

    private static void modifyToNextInt(char[] chs) {
        int d = findDigitToChangeFrom(chs);
        if (d == 0) {
            chs[d] = '1';
        } else {
            chs[d] = (char) (Math.max(chs[d], chs[d - 1]) + 1);
        }
        for (int i = d + 1; i < chs.length; i++) {
            chs[i] = (char) (chs[i - 1] + 1);
        }
    }
}

Assuming 1023 is not valid and instead the answer is 1234, observe the following.
if Input.length() == 0 || Input.length() > 10 then it won't work...

take the first digit of the input, and increment the first digit to get the next digits.
i.e. Input = 2xxx, output = 2345.
It can easily be seen that this is the optimal solution, as every other number starting with 2 smaller than 2345 will have either duplicates, or violate the increasing sequence rule.

This won't work if we need to roll-over. easy way to check for roll-over is if Input.length() > 10 - firstDigit.
if it's rolled over then it's even simpler, just make a 1234... sequence with length = 1 + Input.length()

public int getNextNumber( int number ) {
         if( number >= Integer.MAX_VALUE)
            return -1;

         if( number > -1 && number < 9 ) {
            return number+1;
         }
         number++;
         String word = Integer.toString(number);
         char[] digits = word.toCharArray();
         if( !isUnique( digits) || !isIncremental(digits) )
            return getNextNumber(number);
         return number;

   }

   private boolean isUnique( char [] digits ) {
     HashSet<Character>set = new HashSet<Character>();
     for( char c : digits ){
       if ( set.contains(c) ) return false;
       else
          set.add(c);
     }
     return true;
   }


   private boolean isIncremental(char [] digits ) {

      int prev = -1;
      for(char c : digits ) {
         if (prev > Character.getNumericValue(c))
            return false;
         prev = Character.getNumericValue(c);
      }
     return true;
  }

public int getNextNumber( int number ) {
         if( number >= Integer.MAX_VALUE)
            return -1;

         if( number > -1 && number < 9 ) {
            return number+1;
         }
         number++;
         String word = Integer.toString(number);
         char[] digits = word.toCharArray();
         if( !isUnique( digits) || !isIncremental(digits) )
            return getNextNumber(number);
         return number;

   }

   private boolean isUnique( char [] digits ) {
     HashSet<Character>set = new HashSet<Character>();
     for( char c : digits ){
       if ( set.contains(c) ) return false;
       else
          set.add(c);
     }
     return true;
   }


   private boolean isIncremental(char [] digits ) {

      int prev = -1;
      for(char c : digits ) {
         if (prev > Character.getNumericValue(c))
            return false;
         prev = Character.getNumericValue(c);
      }
     return true;
  }

Basically there are two cases: a. ending with consecutive series of numbers '...6789'; b. start from '123...' if number can't be covered with case a).

public void Test()
        {
            Debug.Assert(124 == GetNumber(000123), "Test [000123] failed");
            Debug.Assert(123 == GetNumber(122), "Test [123] failed");
            Debug.Assert(134 == GetNumber(132), "Test [132] failed");
            Debug.Assert(234 == GetNumber(222), "Test [222] failed");
            Debug.Assert(345 == GetNumber(298), "Test [298] failed");
            Debug.Assert(1234 == GetNumber(789), "Test [789] failed");
            Debug.Assert(1234 == GetNumber(987), "Test [987] failed");
            Debug.Assert(1567 == GetNumber(1543), "Test [1543] failed");
            Debug.Assert(3456 == GetNumber(3333), "Test [3333] failed");
            Debug.Assert(6789 == GetNumber(6788), "Test [6788] failed");
            Debug.Assert(1469 == GetNumber(1468), "Test [1468] failed");
            Debug.Assert(1567 == GetNumber(1543), "Test [1543] failed");
            Debug.Assert(45678 == GetNumber(41543), "Test [41543] failed");
            Debug.Assert(134567 == GetNumber(127777), "Test [127777] failed");
        }

        private int GetNumber(int number)
        {
            int[] digits = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

            // check if number below possible limit
            const int maxNumber = 123456789;
            if (number >= maxNumber)
            {
                throw new Exception(string.Format("Too big number [{0}]", number));
            }

            // negative number produce 0 result
            if (number < 0)
            {
                return 0;
            }

            string numberString = number.ToString(CultureInfo.InvariantCulture);
            int length = numberString.Length;
            int[] numberDigits = numberString.ToCharArray().Select(c => int.Parse(c.ToString(CultureInfo.InvariantCulture))).ToArray();

            List<int> resultDigits = new List<int>(length);

            int prevDigit = 0;
            for (int index = 0; index < length; index++)
            {
                int digit = numberDigits[index];

                // if the digit becomes lower than previous one => skip
                bool mayTakeDigit = prevDigit < digit;

                if (mayTakeDigit && 10 < digit + length - index)
                {
                    // if there is no room for reminder of a kind '...56789' => skip
                    mayTakeDigit = false;
                }

                if (mayTakeDigit)
                {
                    int maxIndexNumber = 0;
                    for (int i = 0; i <= index; i++)
                    {
                        maxIndexNumber += (int)Math.Pow(10, length - 1 - i) * numberDigits[i];
                    }

                    for (int i = 0; i < length - index - 1; i++)
                    {
                        maxIndexNumber += (int)Math.Pow(10, i) * digits[8 - i];
                    }

                    // if there is no enough room of a number of kind (i.e. number > 'xxx56789') => skip
                    mayTakeDigit = number < maxIndexNumber;
                }
                else
                {
                    digit = prevDigit;
                }

                if (mayTakeDigit)
                {
                    resultDigits.Add(index == length - 1 ? 9 : digit);
                }
                else
                {
                    // get consecutive range starting from 'digit + 1'
                    if (index <= length - 1)
                    {
                        if (digit > 0 && digit + length - index < 10)
                        {
                            // if not overcome 10 then finish with '...56789'
                            for (int i = 0; i < length - index; i++)
                            {
                                resultDigits.Add(digit + 1 + i);
                            }
                        }
                        else
                        {
                            // start from '12345...'
                            digit = 0;
                            for (int i = 0; i < length + 1; i++)
                            {
                                resultDigits.Add(digit + 1 + i);
                            }
                        }
                    }

                    break;
                }

                prevDigit = digit;
            }

            int resultNumber = 0;
            for (int i = 0; i < resultDigits.Count; i++)
            {
                resultNumber += (int)Math.Pow(10, resultDigits.Count - 1 - i) * resultDigits[i]; ;
            }

            return resultNumber;
        }

NextNumber(int number)
{
  int numbDigits = numberofdigits(n);
  int [] digits = GetDigits(N+1);
  if(digits.length >9) return -1;
  int default = 123456789;
  bool isdefault = false;
  for(int i=0;i<digits.length ;i++)
  {
    if(9-digits[i]<=digits.length-i-1) { isdefault = true; break;}
    if(i>0 and digits[i]<digits[i-1]) digits[i] = digits[i-1] + 1;
  }
  if(isdefault) return default/(10^(numberofdigits+1))
  else converttonumber(digits);
}

O(d) solution in the number of digits, which is limited to 10 due to int representation limits, so O(1) solution.

int next_larger_asc(int num)
{
    if (num <= 0) return 1;
    int t = num + 1;
    std::vector<int> d;
    while (t > 0)
    {
        d.push_back(t % 10);
        t = t / 10;
    }
    int dn = d.size();
    int carry = 0;
    int ldi = dn; // largest discrepency index
    for (auto i = dn - 1; i > 0; --i)
    {
        if (d[i] >= d[i - 1])
        {
            if (9 == d[i]) carry = 1;
            ldi = i;
            break;
        }
    }
    if (dn == ldi) return num + 1;
    int sai = dn; // smallest ascension index
    for (auto i = ldi; i < dn; ++i)
    {
        if (i + d[i] + carry < 10)
        {
            sai = i;
            break;
        }
    }
    int rv = 0;
    if (dn == sai)
    {
        // have to make a longer number
        if (dn + 1 >= 10) return -1; // can't do it
        for (auto i = 1; i <= dn + 1; ++i)
        {
            rv *= 10; 
            rv += i;
        }
    }
    else
    {
        if (ldi != sai) carry = 1;
        // make ascending sequence from sai
        d[sai] += carry;
        for (auto i = sai - 1; i >= 0; --i)
        {
            d[i] = d[i + 1] + 1;
        }
        // get the new number
        for (auto i = dn - 1; i >= 0; --i)
        {
            rv *= 10;
            rv += d[i];
        }
    }
    return rv;
}

void test_next_larger_asc()
{
    assert(1234 == next_larger_asc(853));
    assert(5678 == next_larger_asc(5432));
    assert(1567 == next_larger_asc(1543));
    assert(1 == next_larger_asc(-3));
    assert(1678 == next_larger_asc(1589));
    assert(16789 == next_larger_asc(15831));
    assert(-1 == next_larger_asc(923456781));
}

Here is very efficient linear time solution.

They key insight to note is that all solutions is a substring of "123456789".
Given this insight, all you have to do is generate all substrings of size k, where k is the length of the input number string. Then return the first substring that is greater then the input string's numeric value.

static String ref = "123456789";
  static int max = 123456789;
  
  public static String nextSequence(String str){
    int num = Integer.parseInt(str);
    if(num > max) return "";
    
    int k = str.length();
    for(int i = 0; i <= ref.length() - k; i++){
      int candidate = Integer.parseInt(ref.substring(i,i+k));
      if(candidate > num){
        return ""+candidate;
      }
    }
    
    if(k+1 <= ref.length()) return ref.substring(0,k+1);
    
    return "";
  }

Here is my solution: Running java code can be found at ideone.com/cTExme

I have taken the liberty of assuming that the example given by the author is wrong and for input 987, the next large value should be 1234.

The basic idea is as follows:

Step1:
First normalize the input number for 9. That is, If the input number has 9 in it then the next larger number is always going to spill into the next significant digit position.
If input has 9 in it, next number larger than current input not having 9 in it can be found using input + amount remaining to reach next significant digit change.
for example
for 192 --> we ned 8 to reach 200.
for 1922 --> we need 88 to reach 2000 etc.
The formula for this is 192+(10-92%10) So depending upon position of 9, 10 changes to 100 or 1000 etc.

Step2:
Now we have the number which does not have 9. So to satisfy requirement 1,2 and 3, get the first digit of that number say that digit is 3 and depending upon the size of the number
(for 20 size is 2, for 1111 size is 4), add next digits (4,5,6 etc) to this number forming next larger positive digit without repetition, incrementing digits and smallest one greater than input.

Edge case:
In Step2, if the first digit happens to be say 8 and the size of the input is 3, then while forming new integer, the value will reach 10. like first digit 8, next digit 9 and 3rd digit 10.
So 8910 wont be a valid 3 digit number. In that case, we have to get the number larger than currently generated number which wont have digits spilling over to 10 when formed a new number.

public class functionReturningInteger {

	public static void main(String[] args) {
		int input = 987;
		
		System.out.println("Next Number for " + input + " is " + nextInteger(input));
	}
	
	private static int nextInteger(int input) {
		
		//Step1 normalize the number for 9
		input = normalizeFor9(input);
		
		//Step2: Now get the first digit of the updated number to form increasing sequence
		int firstDigit = getFirstDigitOfInput(input);
		int sizeOfInput = String.valueOf(input).length();
		
		/*
		 * It may happen that while forming next number of same size, digit may spill over to 10. So get the next larger number which wont spill over to 10.
		 * if the size of the input is going to spill over into 10. The only possible number in that case is the number 1 followed by the size of the input
		 * example if the input is 800, the closes number is going to be 1000
		 */
		if(firstDigit+sizeOfInput > 9) {
			//
			input = (int) Math.pow(10, String.valueOf(input).length());
			firstDigit = getFirstDigitOfInput(input);
			sizeOfInput = String.valueOf(input).length();
		}
		
		StringBuffer finalNumber = new StringBuffer();
		finalNumber.append(firstDigit);
		while(sizeOfInput >finalNumber.toString().length()) {
			finalNumber.append(++firstDigit);
		}
		
		return Integer.valueOf(finalNumber.toString());
	}
	
	//Get the first digit of the given input
	private static int getFirstDigitOfInput(int input) {
		int firstDigit = input / (int) Math.pow(10, String.valueOf(input).length() - 1);
		return firstDigit;
	}
	
	
	/*Start from the right most digit
	 * if number has 9 in it, then increment the input by the place value of 9.
	 * For example on 79, 9 is at position 0 so increment by 1
	 * in 192, 9 is at ten position (position 1), so increment by 192+(10-92%10)
	 * in 933, 9 is at hundred position (position 2), so increment by 933+(100-933%100)
	 * in 19147, 9 is at thousand position (position 3) so increment by 19147+(1000-19147%1000)
	 */
	private static int normalizeFor9(int input) {
		while(findPosition(input,9) != -1) {
			int position = findPosition(input, 9);
			if(position == 0) {
				input++;
			}else {
				input = input + ((int)(Math.pow(10,position)) - input%(int)Math.pow(10,position));
			}
		}
		return input;
	}
	
	//Return the position of 9 in the input. If 9 does not exists, return -1.
	private static int findPosition(int input, int digit) {
		int position = 0;
		while(input != 0) {
			if(input%10 == digit) {
				return position;
			}else {
				input = input/10;
				position++;
			}
		}
		return -1;
	}
}

/*assuming i/p of 987 should not return 1023 as digits in
 * 1023 aren't in incremental sequence
 */

int
num_check(char *num_strP) {
  int *num_arr=(int*)malloc(strlen(num_strP)*sizeof(int));
  int i=0, _ret=1;
  for(i=0; i<strlen(num_strP); i++) {
    num_arr[i]=num_strP[i]-48;
//    printf("dbg: %d\t", num_arr[i]);
  }
  for(i=0; i<strlen(num_strP)-1; i++) {
    if(num_arr[i]>=num_arr[i+1])  _ret =0; 
  }

  free(num_arr);
  return _ret;
}

int
num_checker(int numP) {
  int i=numP;
  char num_str[12]={0};
  while(1) {
    sprintf(num_str, "%d", ++i);
    if(num_check(num_str)){
      break;
    }   
    memset(num_str, 0, 12);
  }
  return i;
}

Here is an example with a unit test included. Basically, if the input is n, we check if (n+1) satisfies the three conditions.

If it does, we return it. If it does not we increment it again and check. We keep incrementing till the result meets all requirements.

And, I assume the OP's example is incorrect. 987's output should be 1234 according to the requirements.

#include <cstdio>

// returns truw if the digits are not in incremental order
bool checkIncremental(int input) {
  bool check = true;
  while (input) {
    // next line checks if the inputs least significant
    // digit is bigger than the second least significant
    // digit or not 
    check = input % 10 > (input/10) % 10;
    if (!check) return true;
   input /= 10; 
  }
  return false;
}

// returns true if there are repeating digits
bool checkRepeat(int input) {
  int copy = input; // make a copy of the input
  if (input < 10)
    return false;    // pigeonhole principle

  if (input > 10000000000)  // not necessary if working with 16-bit ints
    return true;   //pigeonhole principle again

  int lastDigit = copy % 10;
  copy /= 10;
  while (copy){
    if (copy % 10 == lastDigit)
      return true;
    else
      copy = copy / 10; 
  }
  return checkRepeat(input/10);
}


int nextInteger(int input) {
  if (input < 0)
    return 1;
  input++;
  while (checkRepeat(input) || checkIncremental(input) ) 
    input++;
  return input;
}


int main() {
  int i = 1;
  while (i) {
    scanf("%d", &i);
    printf("result %d\n", nextInteger(i));
  }
  return 0;
}

And my function accepts and returns an integer, as opposed to a string. But it is trivial to convert back and forth between them