[Leetcode] 68. Text Justification

https://leetcode.com/problems/text-justification/description/?envType=study-plan-v2&envId=top-interview-150

initial

its a brute force impelemntation but 1 very impt thing is that we dont add spacess at the end of last words. Each line should end with word and not spaces unless it is last line. This is shown in

// Only add spaces if this isn't the last word
                    if(i < index - 1) {
                        // Add base spaces for each gap
                        for(int j = 0; j < spacePerGap; j++) {
                            sb.append(" ");
                        }
                        
                        // Add one extra space for gaps on the left if needed
                        if(extraSpaces > 0) {
                            sb.append(" ");
                            extraSpaces--;
                        }

sol

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        int tmp=0;
        List<String> ans = new ArrayList<>();
        int index=0;
        while(index<words.length){
            // count is number of words in this current line
            int count=0;
            int lineLength=0;
            int startIndex=index;

            while(index < words.length && lineLength+words[index].length()+count<=maxWidth){
                lineLength+=words[index].length();
                count++;
                index++;
            }
            StringBuilder sb = new StringBuilder();

            if(index==words.length || count==1){
                for(int i=startIndex; i<index;i++){
                    sb.append(words[i]);
                    if(i<index-1) sb.append(" ");
                }
                while(sb.length() <maxWidth)sb.append(" ");
            } else{
                int gaps = count-1;
                int spaces = maxWidth-lineLength;

                int spacePerGap = gaps>0 ? spaces/gaps: 0;
                int extraSpaces = gaps>0 ? spaces%gaps :0;

                for(int i= startIndex; i<index;i++){
                    sb.append(words[i]);
                    if(i<index-1){
                        for(int j=0; j<spacePerGap; j++) sb.append(" ");
                        if(extraSpaces>0){
                            sb.append(" ");
                            extraSpaces-=1;
                        }
                    }
                }

            }
            ans.add(sb.toString());
        }
        return ans;
    }
}

complexity

n time and space