import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    public String replaceSpace (String s) {
        // write code here
        if(s==null||s.length()==0){
            return s;
        }
        
        int spaceNum=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)==' '){
                spaceNum++;
            }
        }
        
        int p1=s.length()-1;
        int p2=s.length()+2*spaceNum-1;
        
        char[] temp=new char[p2+1];
        for(int i=p1;i>=0;i--){
            if(s.charAt(i)==' '){
                temp[p2--]='0';
                temp[p2--]='2';
                temp[p2--]='%';
            }else{
                temp[p2--]=s.charAt(i);
            }
        }
        return new String(temp);
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    public String replaceSpace (String s) {
        // write code here
        if(s==null||s.length()==0){
            return s;
        }
        
        StringBuffer sb=new StringBuffer();
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)==' '){
                sb.append("%20");
            }else{
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
        
    }
}

import java.util.ArrayList;
import java.util.Collections;

public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> result=new ArrayList<String>();

        if(str!=null&&str.length()>0){
            DiGui(str.toCharArray(),0,result);
            Collections.sort(result);
        }
        return (ArrayList)result;
    }
    
    public void DiGui(char[] cs,int i,ArrayList<String> list){
        if(cs==null||cs.length==0||i<0||i>cs.length-1) { return ;}
        
        if(i==cs.length-1){
            String val=String.valueOf(cs);
            if(!list.contains(val))
                list.add(val);
        }else{
            for(int j=i;j<cs.length;j++){    ///一定要注意这个地方，要从包含自己，然后再包含其他旋转的
                    swap(cs,i,j);
                    DiGui(cs,i+1,list);
                    swap(cs,i,j);
                } 
            }
            
        }
    
    
    public void swap(char[] cs,int i,int j){
        char temp=cs[i];
        cs[i]=cs[j];
        cs[j]=temp;
    }
    
}

import java.util.*;
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        
        HashMap<Character,Integer> count=new HashMap<Character,Integer>();
        for(int i=0;i<str.length();i++){
            if(count.containsKey(str.charAt(i))){
                count.put(str.charAt(i),count.get(str.charAt(i))+1);
            }else{
                count.put(str.charAt(i),1);
            }
        }
        
        
        for(int i=0;i<str.length();i++){
            if(count.containsKey(str.charAt(i))&&count.get(str.charAt(i))==1){
                return i;
            }
        }
        return -1;
    }
}

public class Solution {
    public String LeftRotateString(String str,int n) {
        if(n==0||str==null||str.length()<=0){
            return str;
        }
        
        int strLength=str.length();
        n=n%strLength;
        char[] temp=new char[str.length()];
        int j=0;
        for(int i=n;i<str.length();i++){
            temp[j++]=str.charAt(i);
        }
        
        for(int i=0;i<n;i++){
            temp[j++]=str.charAt(i);
        }

        
        return new String(temp);
    }
}