import java.util.StringJoiner;
class Solution {
    public String reverseWords(String s) {
        String[] ch = s.split(" ");
        int i =0,j=ch.length/2;
        while(i<j){
            String temp = ch[i];
            ch[i] = ch[ch.length-i-1];
            ch[ch.length-i-1] = temp;
            i++;
        }
        StringJoiner sJoiner = new StringJoiner(" ");
        for(int k =0;k<ch.length;k++){
            if(!ch[k].equals(""))
                sJoiner.add(ch[k]);
        }
        return sJoiner.toString().trim();
    }
}

class Solution {
    public int romanToInt(String s) {
        HashMap<Character,Integer> map =new HashMap<>();
        map.put('I',1);
        map.put('V',5);
        map.put('X',10);
        map.put('L',50);
        map.put('C',100);
        map.put('D',500);
        map.put('M',1000);
        int integerValue = 0;
        int i = s.length()-1;
        while(i>0){
            if(s.charAt(i)=='V' && s.charAt(i-1)=='I'){
                integerValue+=4;
                i=i-2;
            }
            else if(s.charAt(i)=='X' && s.charAt(i-1)=='I'){
                integerValue+=9;
                i = i-2;
            }
            else if(s.charAt(i)=='L' && s.charAt(i-1)=='X'){
                integerValue+=40;
                i = i-2;
            }
            else if(s.charAt(i)=='C' && s.charAt(i-1)=='X'){
                integerValue+=90;
                i = i-2;
            }
            else if(s.charAt(i)=='D' && s.charAt(i-1)=='C'){
                integerValue+=400;
                i = i-2;
            }
            else if(s.charAt(i)=='M' && s.charAt(i-1)=='C'){
                integerValue+=900;
                i = i-2;
            }
            else{

                integerValue+=map.get(s.charAt(i));
                i--;
            }

        }
        if(i==0) integerValue+=map.get(s.charAt(i));
        return integerValue;
    }
}

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;

class GFG {
    public static void main (String[] args) {
        List<String> sentence= new ArrayList<>();
        List<String> queries = new ArrayList<>();
        sentence.add("bob and alice like to text each other");
        sentence.add("bob does not like to ski but does not like to fall");
        sentence.add("Alice likes to ski");

        queries.add("bob alice");
        queries.add("alice");
        queries.add("like");
        queries.add("non occurance");
        System.out.println(get(sentence,queries));

    }
    public static List<List<Integer>> get(List<String> sentence, List<String> q){
        List<List<Integer>> list = new ArrayList<>();
        for(int j =0;j<q.size();j++){
                List<Integer> res = new ArrayList<>();
                String str[] = q.get(j).split(" ");
                for(int i =0;i<sentence.size();i++){
                    String sen = sentence.get(i);
                    boolean present = true;
                    for(String s : str){
                        if(!sen.contains(s)){
                            present = false;
                            break;

                        }
                    }
                    if(present){
                        res.add(i);// sentence index that had s got added
                    }
                }
                if(res.isEmpty()){
                    List<Integer> temp = new ArrayList<>();
                    temp.add(-1);
                    list.add(temp);
                }
                else list.add(res);

            }
        return list;
    }
}

class Solution {
    public String longestPalindrome(String s) {
        //the lcs approach won't work here
        //we will have to use traditional approach of two loops for finding longest
        //palindromic subsequence
        int start=0;
        int length = 1;
        int n = s.length();
        if(n<2) return s;
        for(int i =0;i<n;i++){
            int low = i-1;
            int high = i+1;
            //below will check till how long the index values of high are equal to current index
            //which will be palindrome obviously
            while(high < n && s.charAt(high) == s.charAt(i)){
                high++;
            }
            //same logic as above for low index
            while(low>=0 && s.charAt(low) == s.charAt(i)){
                low--;
            }
            //finally low and high together
            while(low >=0 && high<n && s.charAt(low)== s.charAt(high)){
                low--;
                high++;
            }
            int len  = high-low -1;
            if(len> length){
                length = len;
                start = low+1;
            }

        }
        //if we were to return length of the logest palindromic substring we could have returned 'length';
        return s.substring(start,start+length);
    }
}

class Solution {
    public int compareVersion(String version1, String version2) {
        version1 = version1+".0";
        version2 = version2+".0";
        String[] a = version1.split("\\.");
        String[] b = version2.split("\\.");

        int exL = Math.abs(a.length - b.length);

        if(a.length > b.length){
            char c = '0';
            while(exL-->0){
                version2 = version2+"."+c;
            }
        }
        else {
            char c = '0';
            while(exL-->0){
                version1 = version1+"."+c;
            }
        }


        /// now two strings are equal
        a= version1.split("\\.");
        b = version2.split("\\.");
        System.out.println(a.length + " "+ b.length);
        for(int i =0;i<a.length;i++){
            int p = Integer.parseInt(a[i]);
            int q = Integer.parseInt(b[i]);
            if(p > q) return 1;
            if(p < q) return -1;
        }
        return 0;
    }
}

class Solution {
    List<List<String>> getPartitions(String s) {
        // add logic here 
        List<List<String>> list = new ArrayList<>();
        f(s,0,new ArrayList<>(),list);
        return list;
    }
    public void f(String s, int index, List<String> l,List<List<String>> list){
        if(index>=s.length()){
            list.add(new ArrayList<>(l));
            return;
        }
        for(int i = index;i<s.length();i++){
            if(!isP(s,index,i)) continue;
            l.add(s.substring(index,i+1));
            f(s,i+1,l,list);
            l.remove(l.size()-1);
        }
    }
    public boolean isP(String s, int i,int e){
        while(i<=e){
            if(s.charAt(i++)!=s.charAt(e--)) return false;
        }
        return true;
    }
}