Wednesday, December 21, 2016

Modifying PS1 for bash.

You can change your bash prompt to be more informative:



or



or



or



This prompt is showing the user (root) at IP, the currently opened folder and the git branch if you are in a git repo.

To change your prompt add these lines to ~/.bashrc (for the first prompt shown above)

\[\e[0;31m\] Some Text Here \[\e[m\]

This will color "Some Text Here" red.

parse_git_branch determines the git branch (if you are in a git project directory) and appends it to PS1.

For displaying time you can use : \t or \T. See : (https://www.cyberciti.biz/tips/howto-linux-unix-bash-shell-setup-prompt.html) for more options.

For changing the prompt to look like the second one above:

For the third prompt shown above:

For the fourth prompt shown above:

Monday, December 19, 2016

Searching file names recursively using regex

This perl program searches the current working directory recursively for file names matching the regex supplied by user and prints the results.


Advanced sorting (multiple keys) in perl.

Sometimes you need to sort data like this:
1. Sort by numeric value first.
2. If numeric values are equal, sort by name.

Here's the code for doing this in perl :
Let's suppose I have a hash of hashrefs. (eg. $distance{$city}= $some_number).
This hash stores distances of citites (keys) from a particular city. Now we want to sort by distance first (ascending) and if two citites are at equal distance, we want to sort on the basis of names :


To sort on descending order, we just replace $a with $b and vice versa:

How does this work?

The <=> operator is equivalent to :


so if $a == $b we get to the second test for OR operator which compares the strings similarly. If even the names of strings are equal, we return 0 which tells the sort function that these two entries are equal and order for them doesn't matter to us.


Getting PIDs of all instances of a particular script

This perl code finds the PIDs of all instances of a particluar file.

Let's say you have a file /home/user/script and lets say you have 4 multiple instances of it running on your computer at the same time. You want to find the PIDs of all of them. You can use this :

ps -ef | grep your_file_name | grep -v grep | awk '{print $2}'

You'll have all 4 PIDs separated by a new line character.

Setting system volume on startup (Ubuntu)

This script sets system volume to 0% on Mon-Fri if the system boots up between 8AM to 7PM (so your laptop doesn't shout when you receive some notification).

Otherwise, sets the volume to 100% (when you are at home :D).

#!/usr/bin/perl -w

my ($hour, $wday) = (localtime(time))[2, 6];

open my $log_h, ">>", "/tmp/volume_script_log";

my $vol = ($wday>0 && $wday<6)?(($hour >= 8 && $hour <=19)?0:100):100;

print $log_h "Day of the week is $wday, hour is $hour, setting volume to $vol%\n"; close($log_h);

`amixer -D pulse sset Master $vol%`

For running on start :

Add an entry to crontab file :

#1 (Open crontab file)

crontab -e

#2 (Add this line)

@reboot perl /path/to/thisscript.pl

Friday, October 7, 2016

Running a Process in background even after SSH is closed.

Suppose you have to run a "make" for some large project that you have on a remote server. You have SSH access to it. You want to run that make (or any other) command in background even after you close the SSH connection. Here's how to do it:

1. make myApp > /path/to/output.txt 2>&1 &
   [1] 32568
2. You will see a PID on your command line like the one shown above.
3. disown 32568

You can now close the SSH connection. The output (stdout and stderr) will be in the file specified

/path/to/output.txt

2>&1 redirects the stderr to stdout. More about outputing streams to a file here : (http://askubuntu.com/questions/420981/how-do-i-save-terminal-output-to-a-file see ByteCommander's anwser).


Perl script that checks memory usage of all perl scripts running on a linux machine.

This perl script checks the memory usage of all perl processes running on a linux machine (descending order of memory usage).

Practice Code/Not Very Efficient

#!/usr/bin/perl   

$result = `pidof perl`;
@lines = split ' ', $result;  
scalar @lines or die "No perl processes running at the moment\n"; 

$info;
$index=0; 
while(true){
 $query = "top -b -n 1"; 
 for($i=0;$i<20 && $index!=scalar(@lines);$index++,$i++){
  $query = $query." -p".$lines[$index];
 } 
 $result = `$query`; 
 $result =~ /.*COMMAND(.*)/ms; 
 $result = $1;
 $result =~ s/^\s+//;
 $result =~ s/\s?\Z//; 
 $info = $info.$result;
 if($index==scalar(@lines)){
  last;
 }
} 

@top_result = split '\n', $info; 
#print "No of processes : ".scalar @top_result."\n";
$max = 0; 
@lines2;
@names;

foreach $line (@top_result){
 if($line =~ /\s+(\S+)\s+$/){ 
  if($1 =~ /.*perl.*/){ 
   $line =~ m/(\d+) /;
   $pid = $1;
   if($pid != $$){
    push @lines2, $line;  
    $name = `cat /proc/$pid/cmdline`;   
    push @names, $name;
    if(length($name)>$max){$max = length($name);} 
   } 
  }else{
   push @lines2, $line; 
   $name = $1; 
   push @names, $name;
   if(length($name)>$max){$max=length($name);} 
  }
 } 
}
 
printf '-'x(87+2*$max)."\n";
printf "|%-${max}s | %5s | %7s | %2s | %2s | %6s | %5s | %5s | %1s | %4s | %4s | %8s | %${max}s|\n", "Script Name", "PID", "USER", "PR",
                "NI", "VIRT", "RES", "SHR", "S", "%CPU", "%MEM", "TIME+", "COMMAND";

printf '-'x(87+2*$max)."\n";

$index=0;
foreach $line (@lines2){
 $line =~ /(\S+)\s+\S+\s+\S+\s+$/;    
 $mem = $1; 
 $line = $line." ".$names[$index++];    
 if(!defined($structure{$mem})){
  $structure{$mem} = $line;
 }else{
  $structure{$mem} = $structure{$mem}."\n".$line; 
 } 
} 

@uze = reverse sort {$a <=> $b} keys %structure;  
 
$index=0;
foreach $key(@uze){  
 @op = split '\n', $structure{$key}; 
 foreach $consideration(@op){ 
  @splitt = split ' ', $consideration;
  printf "|%-${max}s | %5s | %7s | %2s | %2s | %6s | %5s | %5s | %1s | %4s | %4s | %8s | %${max}s|\n",
  $splitt[12], $splitt[0], $splitt[1], $splitt[2], $splitt[3], $splitt[4], $splitt[5], $splitt[6],
  $splitt[7], $splitt[8], $splitt[9], $splitt[10], $splitt[11];
  $structure{$splitt[9]} = [@$structure{$splitt[9]}, $line]; 
 }
}
printf '-'x(87+2*$max)."\n"; 


Sunday, March 6, 2016

SPOJ PSTRING (KMP + DP (Recursive)) Solution C++

Problem : www.spoj.com/problems/PSTRING

Algorithm : 

1. Compute KMPs DFA.
2. Apply DP.
  i) Either include a character or skip it.
 ii) Skip a character if it leads to a full substring match.

Code:

#include <iostream>
#include <cassert>
#include <string.h>

using namespace std;
const int mx = 10011 , my = 1024;
int f[my] , trans[my][26];
char X[mx] , Y[my], c ;
int dp[my][mx],xlen,ylen, inf = 1<<30;

#define mini(x, y) (x)<(y)?(x):(y)

int recurse(int matchedLength, int ind){
    if(ind==xlen)return 0;
    if(dp[matchedLength][ind]!=-1)return dp[matchedLength][ind];
    int ret1=inf, ret2=inf, ans=0; 
    int currentMatched = trans[matchedLength][X[ind]-'a'];
    if(currentMatched==ylen){
        ret2 = 1+recurse(currentMatched-1, ind+1);
    }else ret2 = recurse(currentMatched, ind+1);
    ret1 = 1+recurse(matchedLength, ind+1);
    if(ret1==0)ret1 = inf;
    ans = mini(ret1, ret2);
    dp[matchedLength][ind] = ans;
    return ans;
}

int main() {
 int k,i,j;
 while (gets(X)) {
  gets(Y);
  xlen = strlen(X) , ylen = strlen(Y);
  k=0;f[0]=0;
  for(i=1;i<ylen;++i){
      while(k>0 && Y[i]!=Y[k])k = f[k-1];
      if(Y[i] == Y[k])k++;
      f[i] = k;
  }
  for(i=0;i<my;++i)for(j=0;j<mx;++j)dp[i][j]=-1;

  for(i=0;i<ylen;++i){
      for(c='a';c<='z';++c){
          k = i;
          while(k>0 && Y[k] != c)k = f[k-1];
          if(Y[k] == c)k++;
          trans[i][c-'a'] = k;
       }
   }
   printf("%d\n", recurse(0, 0));
 }
}

Friday, March 4, 2016

KMP Substring Match Algorithm (LPS array/Multiple Occurences) - Java

There is another implementation that uses 2D array for transition table of a DFA. Link

Read this first : http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/

Example case:

text: aaabacaabaazq
pat : aabaax

       a a b a a x
lps : [0 1 0 1 2 0]

j = pat index
i = txt index

What do lps values mean?

lps values at any index indicate where in (at what index) we should go in pat so
that our search for the pattern continues in case a mismatch occurs in the middle of successful matching.
If a mismatch occurs at index j in pat, we consider pat[j-1] as the index in pattern string which should be matched next.
Think about prefix suffix match (the tutorial link above) and you'll get the intuition.

For example, if we have matched upto "aa"a in txt 
                                 and "aa"b in pat.

Now the next character is different in both strings (j = 2, i = 2). So we look at lps[j-1] = lps[2-1] = lps[1] = 1.
It means we need to resume our search again at index 1 in pat with the current value of i=2.

Lets see what is at index 1 in pat and index 2 in txt. 

         M
     0 1 2 3 4 5 6 7 8 9
txt: a a a b a c a a b a a z q
pat: a a b a a x

This is good as we did not go to index 1 if we were using bruteforce. We reused the already done computation i.e.
aa in the pat matches upto index 2 in text (beginning at index 1). So we start again at index 3 in txt and index 2 in pat.

Now consider that we already processed
                   |
text: aaabac"aabaa"zq 
pat:  "aabaa"x
             |

so i = 11, j = 5, the indices we are considering now.
A mismatch!, so now look at lps[j-1] = lps[4] = 2
That means we can resume our search with current i the same = 11 and j = 2.
Now we match characters at i = 11, j = 2 in their respective strings.

z!=x.
A mismatch again. But we saved the time for looking at 2 characters "aa"baax in aabaax. If it were bruteforce, we would have
started matching again from the beginning at index 7 in text and index 0 in pat. But now it is index 11 in text and index 2 in pat
that we are matching.

Source :

public class KMPOD {
    static int[] lps;
    static int[] locations;
    
    public static int[] lps(String pat){
        lps = new int[pat.length()];
        
        int i=1, len=0, L = pat.length();
        while(i<L){
            if(pat.charAt(i)==pat.charAt(len)){
                len++;
                lps[i] = len;
                i++;
            }else{
                if(len!=0){
                    len = lps[len-1];
                }else{
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }
    
    public static int[] match(String txt, String pat){
        locations = new int[txt.length()+1];
        int z=1;
        
        int M = pat.length();
        int N = txt.length();
        
        lps(pat);
        
        int j = 0;
        int i = 0;
        
        while(i<N){
            if(pat.charAt(j) == txt.charAt(i)){
                j++;i++;
            }
            if(j==M){
                locations[z++]=(i-j);
                locations[0]++;         //0th index to store the size
                j = lps[j-1];
            }else if(i<N && pat.charAt(j) != txt.charAt(i)){
                if(j!=0) j = lps[j-1];
                else i++;
            }
        }
        return locations;
    }
    
    public static void main(String[] args){
        String text = "aneedleinahaystackneedlehereanotherneedlehere";
        String pat = "needle";
        int[] res = match(text, pat);
        for(int i=1;i<=res[0];++i){
            System.out.println("Match at Index : "+res[i]);
        }
    }
}


Output:

Match at Index : 1
Match at Index : 18
Match at Index : 35


Wednesday, February 17, 2016

ARDA1 SPOJ (Bruteforce / KMP) Solution C++

Bruteforce / KMP

With bruteforce - 0.01s
With KMP        - 0.17s

Solution (Bruteforce):

#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std; 

char s[301][301];
char world[2001][2001]; 

int main(){
 int a, b;  
 scanf("%d %d", &a, &b);  
 for(int i=0;i<a;++i){scanf(" %s", s[i], sizeof(char)*b);}
 int x, y;
 scanf("%d %d", &x, &y); 
 for(int i=0;i<x;++i){scanf(" %s", world[i], sizeof(char)*y);}

 bool g = false; 

 for(int i=0;i<=x-a;++i){
  for(int j=0;j<=y-b;++j){

   if(world[i][j]==s[0][0]){
    bool f = true;
    for(int n=0, i2 = i;i2<i+a;++n, ++i2){
     for(int m=0, j2 = j;j2<j+b;++j2, ++m){
      if(s[n][m]!=world[i2][j2]){
       f = false;break;
      } 
     }
    }
    if(f){
     g = true;
     printf("(%d,%d)\n", i+1, j+1);
    } 
   }  
  } 
 }
 if(!g)printf("NO MATCH FOUND...\n"); 
 return 0;
}

Solution (KMP):

#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;

vector<int> indices;
class KMPSubstringMatch{
public:
 int W, R;
 int **dfa;
 char *s, *sub; 

 KMPSubstringMatch(char *s, char *sub, int subL, int R){
  this->s = s;
  this->W = subL;
  this->sub = sub;
  this->R = R;
  indices.clear();
  dfa = new int*[R];
  for(int i=0;i<R;++i){dfa[i] = new int[W];for(int j=0;j<W;++j)dfa[i][j]=0;}
 }

 ~KMPSubstringMatch(){
  for(int i=0;i<R;++i) delete[] (dfa[i]);
  delete[] dfa;
 }

 void constructDFA(){  
     int X=0;
     dfa[sub[0]][0] = 1;
     for(int i=1;i<W;++i){ 
         for(int j=0;j<R;++j){
             dfa[j][i] = dfa[j][X];
         }
         dfa[sub[i]][i] = i+1;
         X = dfa[sub[i]][X];
     }
 }

 void find(int slength, int sublen){
        int i, j;
        for(i=0, j=0;i<slength;++i){
            j=dfa[s[i]][j]; 
            if(j==W){ 
    indices.push_back(i-sublen+1); 
                j=0;
                i=(i-sublen+1);
            }
        }  
    } 
    
 static void find(char *s, char *sub, int slen, int subL){
        KMPSubstringMatch *kmp = new KMPSubstringMatch(s, sub, subL, 257); 
        kmp->constructDFA();
        kmp->find(slen, subL);
        delete kmp;
    }
};

char s[301][301];
char world[2001][2001];

int main(){
 int a, b;  
 scanf("%d %d", &a, &b);  
 for(int i=0;i<a;++i){scanf(" %s", s[i], sizeof(char)*b);}
 int x, y;
 scanf("%d %d", &x, &y); 
 for(int i=0;i<x;++i){scanf(" %s", world[i], sizeof(char)*y);}

 bool f = false; 
 for(int i=0;i<x;++i){
  int t=0;
  char *cur = world[i];
  KMPSubstringMatch::find(cur, s[t], y, b); 
  if(!indices.empty() && a>1){
   for(int z=0;z<indices.size();++z){
    int v = indices[z]; 
    bool fl = true;
    for(int i2=i, X=0;X<a;++X,++i2){
     for(int j2=v, Y=0;Y<b;++Y,++j2){
      if(s[X][Y]!=world[i2][j2]){fl=false;break;}
     }
     if(!fl)break;
    }
    if(fl){printf("(%d,%d)\n", i+1, v+1);f = true;}
   }
  }else if(!indices.empty() && a==1){
   for(int z=0;z<indices.size();++z){
    int v = indices[z];
    f = true;
    printf("(%d,%d)\n", i+1, v+1);
   }
  }
 }
 if(!f)printf("NO MATCH FOUND...\n");  
 return 0;
}

Tuesday, February 16, 2016

SPOJ BTCODE_H (Maths) Solution - Java

Test Case given-

N = 2, K = 2.

# of words containing only 0 and 1 that are of length 2 -> 4

00
01
10
11

Now insertion of words may happen as:

00 00                      
00 01           01 00
00 10           10 00
00 11           11 00

01 01      
01 10           10 01
01 11           11 01

10 10
10 11           11 10

11 11

Total # cases -> 16.

# cases where trie has 3 nodes = 4
                                4 nodes = 4
                                5 nodes = 8

Expected value of the number of nodes ->

(3*4 + 4*4 + 5*8)                                    68
----------------------         =             ---------------------             =              4.25
          16                                                16

Source (Java):

import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;


public class BTCODE_HSimple {
    
    //Exponentiation by Repeated Sqauring
    public static double power(double a, int b){
        if(b==0)return 1;
        if(b==1)return a;
        if(b%2==1){
            return a*power(a*a, (b-1)/2);
        }else return power(a*a, b/2);
    }
    
    public static void main(String[] args){
        int n = IO.nextInt(); 
        while(n-->0){
            int N = IO.nextInt();
            int K = IO.nextInt();
            double ans = 1;
            for(int i=1;i<=K;++i){
                double p = power(0.5, i); 
                ans += 1;
                double op = 1-p; 
                for(int j=1;j<N;++j){ 
                    ans += power(op, j);
                } 
            }
            System.out.printf("%.2f\n", ans);
        }
    }



    /**************************************IO**************************************/
    
    private static class IO {
        private static InputStream stream = System.in;
        private static byte[] buf = new byte[1024];
        private static int curChar, numChars; 

        private static int read() {
                if (numChars == -1)throw new InputMismatchException();
                if (curChar >= numChars) {
                        curChar = 0;
                        try {
                            numChars = stream.read(buf);
                        } catch (IOException e) {
                            throw new InputMismatchException();
                        }
                        if (numChars <= 0)return -1;
                }
                return buf[curChar++];
        }

        public static int nextInt() {
                int c = read();
                while (isSpaceChar(c))
                        c = read();
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = read();
                }
                int res = 0;
                do {
                    if (c < '0' || c > '9') throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public static char nextChar() {
                int c = read();
                while (isSpaceChar(c)) c = read();
                return (char) c;
        }
        
        private static String nextString(){
            int c = read();
            while(isSpaceChar(c))c=read();
            StringBuilder sb = new StringBuilder();
            do{
                sb.append((char)c);
            }while(!isSpaceChar((c=read())));
            return sb.toString();
        }

        private static boolean isSpaceChar(int c) {
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
        
        private static void println(Object... a){
            for(Object o:a)System.out.print(o);
            System.out.println();
        }
    }
}

Sunday, February 14, 2016

TAP2012D SPOJ (Trie with HashMaps) solution Java

You need to put all the names first and second team players in the same trie. If your logic involves putting the names of team1 into trie and then using team2 player names, you're likely to get WAs. For eg. changing the order of queries for team2 names will get you different answers in some cases.

Check out these test cases:-

5
H HE HER HEREB HEREBY
HEREBY HEREB HERE HER HE

7
THIS IS JUST A SE NT ENCE
SENTTH IS JU SIS AS SE THUS

Check out my solution if you're still stuck.

Source:

import java.io.*;
import java.util.*;
 
class Node{
    HashMap<Character, Integer> children;
    int first =  0;
    int second = 0; 
     
    Node(){
        children = new HashMap<>();  
    }
    
    void init(){
        children.clear(); 
        first = 0;
        second = 0; 
    }
}

class TrieMap {
    static final int MAX = 500000; 
    static int gIndex;
    static Node trie[]; 
    static int count=0;
    
    public static void insert(String s, int type){  
        int cIndex = 0;
      
        for(int i=0;i<s.length();++i){
            char c = s.charAt(i); 
            Integer nIndex = trie[cIndex].children.get(c); 
            if(nIndex==null){ 
                    trie[cIndex].children.put(c, ++gIndex);  
                    if(trie[gIndex]==null)trie[gIndex] = new Node(); 
                    trie[gIndex].init();
                    cIndex = gIndex; 
                    nIndex = cIndex;  
            }else{
                cIndex = nIndex;  
            }
            
            if(type==1)trie[nIndex].first++; 
            else       trie[nIndex].second++;
        }  
    } 
    
    static int ans=0;
    public static int query(int cIndex, int depth){  
        
        int sub = 0;
        for(Map.Entry<Character, Integer> me:trie[cIndex].children.entrySet()){ 
            int value = me.getValue();
            
            if(trie[value].first>0 && trie[value].second>0){
                int r = query(value, depth+1);
                sub+=r;
                trie[cIndex].first -= r;
                trie[cIndex].second -= r;
            }
        } 
        int min  = Math.min(trie[cIndex].first, trie[cIndex].second); 
        if(cIndex!=0)ans+=depth*min; 
        return min+sub;
    } 
    
    public static void main(String[] args){
          
        trie = new Node[MAX];  
        
        while(true){ 
            int n = IO.nextInt();
            if(n==-1)return;
            trie[0] = new Node();
            trie[0].init();  
            count=0;
            gIndex = 0;
            for(int i=0;i<n;++i){
                String s = IO.nextString(); 
                insert(s, 1);
            } 
            ans=0; 
            for(int i=0;i<n;++i){  
                insert(IO.nextString(), 2);  
            }   
            query(0, 0);
            IO.println(ans);
        }
    }
    




    /***********************************IO***************************************/
    private static class IO {
        private static InputStream stream = System.in;
        private static byte[] buf = new byte[1024];
        private static int curChar, numChars; 

        private static int read() {
                if (numChars == -1)throw new InputMismatchException();
                if (curChar >= numChars) {
                        curChar = 0;
                        try {
                            numChars = stream.read(buf);
                        } catch (IOException e) {
                            throw new InputMismatchException();
                        }
                        if (numChars <= 0)return -1;
                }
                return buf[curChar++];
        }

        public static int nextInt() {
                int c = read();
                while (isSpaceChar(c))
                        c = read();
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = read();
                }
                int res = 0;
                do {
                    if (c < '0' || c > '9') throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public static char nextChar() {
                int c = read();
                while (isSpaceChar(c)) c = read();
                return (char) c;
        }
        
        private static String nextString(){
            int c = read();
            while(isSpaceChar(c))c=read();
            StringBuilder sb = new StringBuilder();
            do{
                sb.append((char)c);
            }while(!isSpaceChar((c=read())));
            return sb.toString();
        }

        private static boolean isSpaceChar(int c) {
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
        
        private static void println(Object... a){
            for(Object o:a)System.out.print(o);
            System.out.println();
        }
    }
}

Saturday, February 13, 2016

LEONARDO SPOJ (Implementation) Solution - JAVA

Algorithm :-

1. Odd length cycles are OK.
2. The graph should have two even length cycles of the same length if even cycles exist. (There may be multiple even cycles).
3. Self loops are OK.

Point #2:

Consider an alphabet having only 6 letters i.e. ABCDEF. Now we have to apply the same permutation twice to get "CDEABF". The permutation we apply is "BCDAEF". Applying it twice (steps):-

|--->CDABEF
P
|--->BCDAEF
P
|----ABCDEF

Where P stands for the application of the permutation "BCDAEF". Now if we only consider the final alphabet string and the original one,

CDABEF

ABCDEF

Notice our even length cycle "BCDA" has split up into two even cycles of equal length. (CA and DB).

You can similarly figure out that odd length cycles remain odd length cycles and of course, self loops have no effect.

Self loops:

There are two self loops in the above example E-E and F-F.

Now just write code to check whether there are even number of even length cycles. If this is the case, the answer is yes, otherwise no.

Source (Java):

import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;


public class LEONARDO { 
    
    public static void main(String[] args){
        int n = IO.nextInt();
        String REF = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        while(n-->0){
            String s = IO.nextString();
            
            int[] pos = new int[256];
          
            for(int i=0;i<s.length();++i){
                pos[s.charAt(i)] = i;
            }
            
            boolean m[] = new boolean[256]; 
            
            int cyclesReg[] = new int[26]; 
            for(int i=0;i<s.length();++i){
                char c = s.charAt(i); 
                boolean f = false;
                int length =0 ;
                while(!m[c]){  
                    f = true;
                    length++;
                    m[c] = true;
                    int p = pos[c];
                    c = REF.charAt(p);
                } 
                if(f){ 
                    cyclesReg[length]++;
                }
            }
             
            boolean f = true;
            for(int i=0;i<cyclesReg.length;++i){
                if(i%2==0 && cyclesReg[i]%2!=0){f =  false;break;}
            }
            if(f)IO.println("Yes");
            else IO.println("No");
        }
    }
    
    private static class IO {
        private static InputStream stream = System.in;
        private static byte[] buf = new byte[1024];
        private static int curChar, numChars; 

        private static int read() {
                if (numChars == -1)throw new InputMismatchException();
                if (curChar >= numChars) {
                        curChar = 0;
                        try {
                            numChars = stream.read(buf);
                        } catch (IOException e) {
                            throw new InputMismatchException();
                        }
                        if (numChars <= 0)return -1;
                }
                return buf[curChar++];
        }

        public static int nextInt() {
                int c = read();
                while (isSpaceChar(c))
                        c = read();
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = read();
                }
                int res = 0;
                do {
                    if (c < '0' || c > '9') throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public static char nextChar() {
                int c = read();
                while (isSpaceChar(c)) c = read();
                return (char) c;
        }
        
        private static String nextString(){
            int c = read();
            while(isSpaceChar(c))c=read();
            StringBuilder sb = new StringBuilder();
            do{
                sb.append((char)c);
            }while(!isSpaceChar((c=read())));
            return sb.toString();
        }

        private static boolean isSpaceChar(int c) {
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
        
        private static void println(Object... a){
            for(Object o:a)System.out.print(o);
            System.out.println();
        }
    }
}