CareerCup

This is 0-1 knapsack problem where the thief wants to steal maximum number of items. Max given is sack limit and the word lengths are items weight here.

for j from 1 to max:
	for all i if array[i] < j:
		sol[j] = max(sol[j], 1 + sol[j - array[i]])
return sol[max]

Based on this:
"Let's say I have a word "I love chicken", I can break the number of characters in each word, like so: [1] [4] [7] [1,4] [4,7], [1,4,7]."
we need to consider the provided ordering of the array in order to construct valid phrases. This suggests that we should NOT sort the input array.

We are looking for the longest phrase.. which means the longest continues sub-sequence in this array where the sum <= max.

public static int longestPhraseWith(int[] input, int max) {
        if (input == null || input.length == 0 || max <= 0) {
            return 0;
        }

        int i = 0;
        while (input[i] > max) {
            i++;
        }

        if (i >= input.length) {
            return 0;
        }

        int words = 1, maxWords = 1;
        int leftIndex = i;
        int sum = input[i];

        for (int j = i + 1; j < input.length; j++) {
            sum += input[j];
            words++;
            if (sum <= max) {
                maxWords = Math.max(maxWords, words);
            }
            else {
                while (sum > max && leftIndex <= j) {
                    sum -= input[leftIndex++];
                    words--;
                }
            }
        }

        return maxWords;
    }

This is the c++ implementation.
I think we can simply find the longest subsequence
whose sum is no greater than max.

int longestSubseqMaxSum(const vector<int> &arr, int maxSum)
{
        int p1 =0, p2 = 0;
  int S = arr[0];
  int maxLen = 0;

  if(S <= maxSum)
    maxLen = 1;

  while(p2 < arr.size() - 1){
    if(S <= maxSum){
      S += arr[++p2];
    }
    else {
      S -= arr[p1++];
    }

    if(S <= maxSum && p2 - p1 + 1 > maxLen)
      maxLen = p2 - p1 + 1;
  }

  return maxLen;
}

This is the test result

arr = {1, 4, 7, }, max = 5
result = 2

arr = {3, 1, 2, 3, }, max = 4
result = 2

arr = {3, 1, 1, 2, 5, 1, 2, 1, 2, }, max = 10
result = 5

def longest_phrase(a, n):
    max_words = 0
    start = 0
    end = 1
    
    while end < len(a):
        sum_chars = sum(a[start:end])
        print sum_chars, start, end
        if sum_chars <= n:
            end += 1
        else:
            max_words = max(max_words, end -1 - start)
            start += 1
    if sum(a[start:end]) <= n:
        max_words = max(max_words, end - start)
    else:
        max_words = max(max_words, end -1 - start)
            
    return max_words

a =  [1,4,7]
print longest_phrase(a, 5)

A C++ solution

This problem is neat because you naturally want to sort such a problem, but the words need to remain next to each other. The solution below uses the concept of a queue in that it pushes values onto a sum, and pops off the oldest value (found by "i - len"). Also this algorithm doesn't bother reducing the length ever as the length essentially "raises the bar" for the next max length.

Time: O(n)
Space: O(1)

int maxLen(int arr[], int max, int count)
{
  // Corner cases and edge cases
  if (count < 1 || max < 1) return 0;
  
  int sum = 0;
  int len = 0;
  
  for (int i = 0; i < count; ++i)
  {
    sum += arr[i];
    
    if (sum <= max)
      ++len;
    else
      sum -= arr[i - len];
  }
  
  return len;
}

what is output?

This solution takes O(n) time.

int careercup(int[] array, int max){
	if(max <= 0)
		return 0;

	int size = array.length;
	int left = 0;
	int sum = 0;

	int count = 0;
	int maxCount= 0;

	for(int i = 0; i < size; i++){
		int word = array[i];
		if(sum + word <= max){
			sum += word;
			count++;
		}else{
			if(count > maxCount)
				maxCount = count;
			
			sum += word;
			while(left <= i && sum > max){
				sum -= array[left];
				left++;
				count--;
			}			
		}

	}

	if(count > maxCount)
		maxCount = count;

	return maxCount;

	


}

Sort the array and iterate till we the sum is less than equal to max.
O(nlogn) sorting complexity

The trick part is to sort the array, ones sorted becames into the problem of find a continius sequence that sums until max,every time we find a value <= max we update the maximum of words.

public int GetMaxNumberWords(int[] array, int max)
{
	if (array == null || array.Length == 0)
		return 0;
	
	Array.Sort(array);
	
	int i = 0;
	int j = 0;
	int maxWords = int.MinValue;
	int sum = array[0];
	
	while (i < array.Length)
	{
		if (a[i] > max)
			break;
		
		if (sum <= max)
		{
			int numWords = i - j + 1;
			maxWords = Math.Max(maxWords, numWords);
		}
		
		Console.WriteLine("sum = " + sum + ", i = " + i + ", j = " + j + ", maxMords = " + maxWords);
		
		if (i == j || sum < max)
		{
			i++;
			if (i < array.Length)
				sum += array[i];
		}
		else
		{
			sum -= array[j];
			j++;
		}
	}
	
	return maxWords == int.MinValue ? 0 : maxWords;
}

Algorithm: Please suggest whether we can solve in this way dont mind about the pseudocode i m practising to write it :)

1. take two stack S1 and S2.
2. fill S1 with items in the array from rear end.
3. initiate sum=0 count=0 and max=given value
4. while(!S1.empty()){
int val = s1.pop();
if((sum+val)<=max){
count++;
sum=sum+val;
s2.push(val);
}else{
s1.push(s2.pop());
sum=0;
}}
if(s2.pop()<=max){
count++;
}

}

package com.algo.clrs23;

import java.util.Stack;

public class LongestPhrase {

public static int longestPhrase(int[] inputs,int max) {

Stack<Integer> S1 = new Stack<>();
Stack<Integer> S2 = new Stack<>();
int sum = 0;
int count=0;
for (int i = inputs.length-1; i >=0; i--) {
S1.push(inputs[i]);
}
while(!S1.isEmpty()) {

int val = S1.peek();
int addition = sum+val;
if(addition<=max) {
++count;
sum=sum+val;
S2.push(S1.pop());
}else {
sum=0;
S1.push(S2.pop());
}
}
if(S2.peek()<=max){
++count;;
}
return count;
}
public static void main(String[] args) {

int[] inputs = {3,1,2,3};
int max=5;
int output = LongestPhrase.longestPhrase(inputs, max);
System.out.println(output);


}

}

1. Sort the array string by length
2. iterate over it and get longest and second longest string length
3. print it.
//-----Replace the string with any desired string and also key with any key.

import java.util.Arrays;
import java.util.Comparator;


public class LongestPhraseString
{
    //~ Methods ----------------------------------------------------------------


    public static void countString( String[] inp, int length )
    {
        Arrays.sort( inp, new Comparator<String>( )
            {
                public int compare( String s1, String s2 )
                {
                    return s1.length( ) - s2.length( );
                }
            } );

        int longestStringLen = 0;
        String longestString = "";

        int secondLongestStringLen = 0;
        String secondLongestString = "";

        int count = 0;
        boolean flag = false;

        for ( int i = inp.length - 1; i >= 0; i-- )
        {
            System.out.println( inp [i] );

            if ( inp [i].length( ) <= length )
            {
                if ( count == 0 )
                {
                    longestStringLen = inp [i].length( );
                    longestString = inp [i];
                }
                else if ( inp [i + 1].length( ) > inp [i].length( ) )
                {
                    if ( flag == false )
                    {
                        secondLongestStringLen = inp [i].length( );
                        secondLongestString = inp [i];
                        flag = true;
                    }
                }

                count++;
            }
        }

        System.out.println( "[" + secondLongestStringLen + " , " +
              longestStringLen + "]" );
        System.out.println( "[" + secondLongestString + " , " + longestString +
              "]" );
    }


    public static void main( String[] args )
    {
        String inp = "I love chicken";

        String[] inpStr = inp.split( " " );

        countString( inpStr, 5 );
    }
}

Couldn't you just use a min-heap and then pull from the top of the heap until you reach the max?

int findLongest(vector<int> v, int max)
{
    int soFar = 0, best = 0, p1 = 0, p2 = 0, nWords = 0;
    int start = 0, end = 0;

    while (p2 < v.size()) {
        soFar += v[p2];

        if (soFar > max) {
            while (p1 < p2 && soFar > max) {
                soFar -= v[p1];
                p1++;
            }
            while (p2 < v.size() && v[p2] > max) {
                p2++;
                p1 = p2;
                soFar = 0;
            }
        }

        if (p2 - p1 + 1 > best) {
            best = p2 - p1  + 1;
            start = p1;
            end = p2;
        }
        p2++;
    }

    cout << "start = " << start << endl;
    cout << "end = " << end << endl;
    return best;
}

/**
Optimized by remembering previous length and previous sum

*/


public class WordLengthFunction {
    
    
    public static void main(String args[]) {
        int input[] = {3, 1, 2, 3};
        int max = 4;
        
        
        System.out.println(findLength(input, max));
        
    }

    private static int findLength(int[] input, int max) {
        int maxLength = 0;
        
        int psum = 0;
        int plength = 0;
        
        for(int i=0; i< input.length; i++) {
            int sum = 0;
            
            if(psum != 0) {
                sum = sum - input[i -1];
            }
            
            int ci = (plength <= 1) ? i : i + plength + 1;
            
            for(int j = ci; j < input.length; j++) {
                if(sum + input[j] <= max) {
                    sum = sum + input[j];
                    ci = j;
                } else {
                    break;
                }
            }
            int clength = (ci == i) ? 0 : ci - i + 1;
            maxLength = Math.max(maxLength, clength);
        }
        return maxLength;
    }
}