CareerCup

Given info: Width of the page = N, A vector of words (of length K)

For simplification of logic, I assume start index = 1.

Idea: Let l_i be the length of ith word. For a meaningful sentence there must be
at least one space after every word (except the last word). Then total MINIMUM length
needed is [sum(l_i) i=1 to K] + (K-1) = M.

Sanity check: If M>N => not acceptable => error/return

If (N>M), we need to accommodate (N-M) additional spaces after first K-1 words.
Let x = (N-M)/(K-1). y= (N-M)%(K-1).

for each word of first K-1 words:
if word index is <= y => number of spaces next to it = 1+x+1; // default space + additional spaces
else word index >y => number of spaces next to it = 1+x;// default space + additional spaces

Concatenate the words into one string with spaces as defined above.

1. calculate number of space between words: here it is 2
2. calculate number of space to be distributed : here 15-11 = 4
3. each space between words will have additional space: 4/2 and either first or last space will have 4%2 (here 0, so distribution is common) additional space

finally: "DOG<space><space><space>IS<space><space><space>CUTE"

Assuming page width >= lenth of the sentence

1. Calculate the number of words and total letters.
2. if total_words != 1 then 
  2.1 Extra_width = (page width - total_letter_count)
  2.2 space_in_bet_words = total_wrods - 1 
  2.3 each_word_spacing = Extra_width / space_in_bet_words
  2.4 Extra_width = Extra_width % space_in_bet_words
  2.5 fill the extra width by putting extra spaces not in between consecutive word rather than first spacing, last spacing, second spacing, second last spacing etc like that.
3. else
  3.a align the word in the middle. Divide the extra spaces by half. If not divisible by 2, Then add the extra space in the front (by design). So the style would be more like (<spaces(may be extra one)> <Word> <Spaces>)

1. count no. of spaces in the sentence( say nos)
2. calculate diff = page width - sentence length - nos
3. calculate diff/nos. replace all spaces by this number of spaces.
4. calculate xtra = diff%nos. add one extra space to every space and dcrement xtra untill xtra is zero.

char* Adjust(char* s, int width)
{
    //TODO: argument validation
    
    //
    //get number of words
    //
    int cWords = 0; // number of words
    bool IsWord = false;
    char* p = s;    // pointer to s
    
    while(*p != '\0')
    {
        if(*p==' ')
        {
            IsWord = false;         
        }
        else
        {
            if(!IsWord)
            {
               IsWord = true;
               cWords++;
            }            
        }
        p++;
    }
    
    //
    //compute extra space distribution
    //

    int cExtraSpaces = width - strlen(s);

    int dist, remain;
    if(cWords > 1)
    {
       dist = cExtraSpaces/(cWords-1);
       remain = cExtraSpaces%(cWords-1);
    }
    else
    {
       ASSERT(FALSE);
    }

    //
    //copy and insert spaces.
    //
    
    //create buf for new string
    char* s2 = new char[width+1];
    s2[width]='\0';

    p=s;
    int idxS2=0; // index to iterate through s2
    IsWord = false;
    int cWords2 = 0; // word count visited in s

    while(*p != '\0')
    {
        if(*p == ' ')
        {
            IsWord = false;                              
        }
        else
        {
            if(!IsWord)
            {
                cWords2++;
                IsWord = true;
                if (cWords2 > 1)
                {
                   int cSpacesInsert = cExtraSpaces;
                   if(remain>0)
                   {
                       cSpacesInsert++;
                       remain--;
                   }

                   for(int i=0;i<cSpacesInsert;++i)
                   {
                       s2[idxS2++]=' ';
                   }
                }
            }
        }

        s2[idxS2++] = *p;
    }

    return s2;
}

seriously dude!! you asking this question ? :P

The question itself is pretty vague, can there be spaces between chars in a word as well? Otherwise this seems trivial. Considering a line with a single word, since there should be no spaces before and after, how would that case work?

I think requirement is not clear. Think of an use case where word is just "TEST" so how would you align this word on entire page width.

public void adjustPageWidth(String s, int pageWidth){
		if(s.length()>1){
		String [] words = s.split("\\s");
		int space = words.length-1;
		int totalSpace = space+(pageWidth-s.length());
		space = totalSpace/(words.length-1);
		int xtraSpace = totalSpace%(words.length-1);
		StringBuffer str = new StringBuffer();
		if(s.length()==pageWidth){
			System.out.println("sentence already adjusted");
		}
		else{
			for(int i =0;i<words.length;i++){
				int temp = space;
				str.append(words[i]);
				while(temp>0){
					str.append(" ");
					temp--;
				}
				if(xtraSpace>0){
					str.append(" ");
					xtraSpace--;
				}
				
			}
		}
		System.out.println(str);
		}
		System.out.println("orginal string-->" + s);
	}

This should work for strings with length>1. The algorithm inserts the spaces in between the words. But here the complexity is not O(n).

qss

#include <iostream>
#include <string>
using namespace std;

int main() 
{
  char str[] = "The quick brown fox jumps over the lazy dog";
  int  wd = 200; 
  int  num_space = 0;
  int  num_allspace;
  int  mul_space;
  int  temp1,temp2;

  int len = strlen(str);
  
  if(wd<len){
    cout<<"space not enough!"<<endl;
  } else if(wd == len){
    cout<< str << endl;
  } else {
    for(int i=0; i<len; i++){
      if(str[i]==' ') num_space += 1;
    }
    num_allspace = wd - len;
    mul_space = num_allspace/num_space;
    temp1 = num_allspace%num_space;
    
    
    for(int i=0; i<len; i++){
      if(str[i]==' '){
        temp2 = (temp1 > 0)?1:0;
        cout << string(mul_space+temp2,' ');
        temp1 -=1;
      }
      else
        cout << str[i];
    }
  }
  return 0;
}

import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class SpaceAdjustment {

	Pattern pattern = Pattern.compile( "\\s" );
	public static final int NUMBER_OF_CHARACTERS = 15;

	public String adjust(String input) {

		if ( isNull( input ) ) {
			return null;
		}

		if ( input.isEmpty() ) {
			return returnSpaces();
		}

		List<String> list = new ArrayList<String>();

		addString( input, list );

		String res = "";
		int count = 0;
		for ( String str : list ) {

			if ( count >= 1 ) {
				res += "\n";
			}

			res += doAdjust( str );
			count++;
		}

		return res;
	}

	private boolean isNull(String input) {

		if ( input == null ) {
			return true;
		}

		return false;
	}

	private String returnSpaces() {
		String res = "";
		for ( int i = 0; i < NUMBER_OF_CHARACTERS; i++ ) {
			res += " ";
		}

		return res;
	}

	private void addString(String input, List<String> list) {

		if ( input.length() < NUMBER_OF_CHARACTERS ) {
			list.add( input );
		}
		else {
			splitInput( input, list );
		}
	}

	private void splitInput(String input, List<String> list) {

		int startIndex = 0, endIndex = NUMBER_OF_CHARACTERS;

		while ( true ) {

			list.add( input.substring( startIndex, endIndex ) );

			if ( endIndex == input.length() ) {
				break;
			}

			startIndex = endIndex;
			endIndex = endIndex + ( input.length() - endIndex );
		}
	}

	private String doAdjust(String input) {

		int spaceLeft = getNumberOfSpacesLeft( input, NUMBER_OF_CHARACTERS );
		int spaceDiff = 0;
		Matcher matcher = pattern.matcher( input );

		List<Integer> minSpaceList = new ArrayList<Integer>();
		StringBuilder str = new StringBuilder( input );
		while ( matcher.find() ) {

			spaceDiff = matcher.end() - matcher.start();
			System.out.println( "start: " + matcher.start() + " end: " + matcher.end() + " spaceDiff: " + spaceDiff
					+ " spaceLeft: " + spaceLeft );

			if ( spaceDiff < spaceLeft ) {
				minSpaceList.add( matcher.start() );
			}
		}

		if ( !minSpaceList.isEmpty() ) {

			System.out.println( "minSpaceList size: " + minSpaceList.size() + " space size: "
					+ ( spaceLeft / minSpaceList.size() ) );

			int offset = 0;

			for ( int index : minSpaceList ) {
				System.out.println( "index: " + index );

				index += offset;
				if ( minSpaceList.size() == 1 ) {
					int indx = index;
					for ( int i = 0; i < 2; i++ ) {
						for ( int j = 0; j < ( spaceLeft / 2 ); j++ ) {
							str.insert( indx + j, " " );
						}
						
						indx = str.length();
					}
				}
				else {
					for ( int i = 0; i < ( spaceLeft / minSpaceList.size() ); i++ ) {
						str.insert( index + i, " " );
						offset++;
					}
				}
			}
		}

		return str.toString();
	}

	private int getNumberOfSpacesLeft(String input, int numberOfCharacters) {

		return numberOfCharacters - input.length();
	}
}

python:

import sys

def leftRightJustify(words, width):
	# print words as a paragraph with (width) width
	# each line shall be left and right justified
	i = 0
	while i < len(words):
		w_len = len(words[i])
		if w_len > width:
			print
			print 'ABORT: CANNOT CONTAIN WORD'
			return
		# current length of line
		c_len = 0
		line = []
		n_space = width
		n_words = 0
		while c_len + w_len <= width:
			line.append(words[i])
			# current length shall contain a space for a whitespace
			c_len += w_len+1
			n_words += 1
			i += 1
			if not (i < len(words)):
				break
			w_len = len(words[i])
		# we added n_words number of extra whitespaces in the length
		n_space = width - c_len + n_words + 1
		# at least put this number of spaces between two words
		n_space_each  = n_space / (n_words-1)
		# if we equally distribute all spaces inbetween the words
		# how many extra spaces we are left with
		n_extra_space = n_space % (n_words-1)

		for n in xrange(0, len(line)):
			sys.stdout.write(line[n])
			sys.stdout.write(' ' * n_space_each)
			if n_extra_space > 0:
				sys.stdout.write(' ')
				n_extra_space -= 1
		print

if __name__ == '__main__':
	words = "In my younger and more vulnerable years my father gave me some advice that I've been turning over in my mind ever since. 'Whenever you feel like criticizing any one,' he told me, 'just remember that all the people in this world haven't had the advantages that you've had.' He didn't say any more, but we've always been unusually communicative in a reserved way, and I understood that he meant a great deal more than that. In consequence, I'm inclined to reserve all judgments, a habit that has opened up many curious natures to me and also made me the victim of not a few veteran bores. The abnormal mind is quick to detect and attach itself to this quality when it appears in a normal person, and so it came about that in college I was unjustly accused of being a politician, because I was privy to the secret griefs of wild, unknown men. Most of the confidences were unsought - frequently I have feigned sleep, preoccupation, or a hostile levity when I realized by some unmistakable sign that an intimate revelation was quivering on the horizon; for the intimate revelations of young men, or at least the terms in which they express them, are usually plagiaristic and marred by obvious suppressions. Reserving judgments is a matter of infinite hope. I am still a little afraid of missing something if I forget that, as my father snobbishly suggested, and I snobbishly repeat, a sense of the fundamental decencies is parcelled out unequally at birth.".split(' ')
	leftRightJustify(words, 50)