CareerCup

#include <iostream>
#include <stdlib.h>

using namespace std;

int solution(char* str)
{
int characterCount[26]={0};
int* characterPositionList[26]={0};
int characterPositionListIndex[26]={0};

int sum=0,left=0,right=0,len=0,flag=0;

for(;str[len]!='\0';len++)
{
characterCount[str[len]-'A']++;
}

cout<<"len="<<len<<endl;

for(int i=0;i<26;i++)
{
if(characterCount[i])
{
characterPositionList[i] = new int[characterCount[i]];
}
}

for(int i=0;i<len;i++)
{
characterPositionList[str[i]-'A'][characterPositionListIndex[str[i]-'A']++] = i;
}

for(int i=0;i<26;i++)
{
if(characterPositionList[i])
{
sum+= characterPositionList[i][0]-0;
int j=1;
for(;j<characterCount[i];j++)
{
sum+= ((characterPositionList[i][j]-characterPositionList[i][j-1]-1)*2);
}
sum+= (len - characterPositionList[i][j-1]- 1);
//sum++;
left = characterPositionList[i][0]-0;
if(characterCount[i]>1)
{
right = characterPositionList[i][1]-characterPositionList[i][0];
sum+= (left*right);
for(j=2;j<characterCount[i];j++)
{
left = characterPositionList[i][j-1]-characterPositionList[i][j-2]-1;
right = characterPositionList[i][j]-characterPositionList[i][j-1]-1;
sum+= (left*right);
}
left = characterPositionList[i][j-1]-characterPositionList[i][j-2]-1;
}
right = len-characterPositionList[i][j-1]-1;
sum+= (left*right);
sum+= characterCount[i];
}
}

return sum;
}




int main()
{
char str[]="ACAX";
cout<<solution(str)<<endl;
}

Could you please add more comments in this code. or Explain your algo.

Java Solution

private int sum=0;
  public int substringSum(String str) {
    boolean[] visited  = new boolean[str.length()];
    calSubstringSum(str,0,visited);
    return sum;
  }

  private void calSubstringSum(String str,int index,boolean[] visited)
  {
    if(index>str.length()-1 || visited[index])
      return;

    String temp="";
    for(int i=index;i<str.length();i++)
    {
      temp+=str.charAt(i);
      visited[i]=true;
      sum+=getSum(temp);
      calSubstringSum(str,i+1,visited);
    }
  }

  private int getSum(String str)
  {
    int count=0;
    int[] map = new int[26];
    for(char c: str.toCharArray())
    {
      map[c-'A']++;
    }

    for(int i:map)
    {
      if(i==1)
        count++;
    }
    return count;
  }

posting code with comments

#include <iostream>
#include <stdlib.h>

using namespace std;

int solution(char* str)
{
    //array to hold count of occurance of 26 alphabets a-z
    int characterCount[26]={0};
    int* characterPositionList[26]={0};
    int characterPositionListIndex[26]={0};
    
    int sum=0,left=0,right=0,len=0,flag=0;

    //loop from begining of str to end of str
    for(;str[len]!='\0';len++)
    {
        //str[len]-'A' converts the alphabet to int representation
        //example->if str[len] is 'A', 'A'-'A' = 0 which is the 1st index of characterCount[]
        //if str[len] is 'Z', 'Z'-'A' = 25 which is the 26th index of characterCount[] 
        characterCount[str[len]-'A']++;
    }
   
    cout<<"len="<<len<<endl;

    //loop from begining of characterCount[] to end
    for(int i=0;i<26;i++)
    {
        //if characterCount[i] is not zero, means alphabet at position has count greater than zero
        if(characterCount[i])
        {
            //create characterPositionList[i][j], where each individual element of characterPositionList[i]is a pointer to integer array
            //in ith position of characterPositionList,create another integer array
            //where i indicates the alphabet like in characterCount[i]
            //where j indicates the next occurrence of the same alphabet so that characterPositionList[i][j] is the position of the next occurence of alphbet in input array str[]
            //example in "ACAX", there are 2 occurences of A at str[0] and str[2] and total number of occurences of 'A'=2
            //so characterPositionList[0] points to array of length 2, where characterPositionList[0][0]=0 and characterPositionList[0][1]=2
            //the new array that characterPositionList[i] points to is populated in next for loop 
            characterPositionList[i] = new int[characterCount[i]];
        }
    } 

    for(int i=0;i<len;i++)
    { 
        //the new array that characterPositionList[i] points to is populated here
        //characterPositionListIndex[i] points to last element j of characterPositionList[i][j] for a given i
        characterPositionList[str[i]-'A'][characterPositionListIndex[str[i]-'A']++] = i;
    }

    for(int i=0;i<26;i++)
    {
        if(characterPositionList[i])
        {
            //consider "ACAX" and character 'C'(ie, characterPositionList[1][0]),so the character starts at position1,ie,characterPositionList[2][0]=1, call it k.
            //So it can form k+1 substrings that we can consider,ie, "AC" and "C", takinginto countfrom begining till this character
            //but we consider 1-character substrings atthe end separately with the statement "sum+=characterCount[i]"(there can be characterCount[i] 1-character substring)
            //so, we exclude 1-character-substring and consider k only.
            sum+= characterPositionList[i][0]-0;
            int j=1;
            for(;j<characterCount[i];j++)
            {
                //here consider thecharacter 'A'. It has 2 positions in "ACAX",at 0 and 2.
                //we calculate the number of characters in between excluding 'A's.There is only 1 'C'.
                //the number of substrings itcan form with left-side 'A'is 1,ie,"CA" and with right is 1,ie,"AC". So, the result is multiplied by 2 forleft-side calculation andright-side calculation
                sum+= ((characterPositionList[i][j]-characterPositionList[i][j-1]-1)*2);
            }
            //Simmilar to "sum+= characterPositionList[i][0]-0", it considers the numberofsub-strings thatcan be formed from lastoccurence ofan alphabet to end of string
            sum+= (len - characterPositionList[i][j-1]- 1);
            //sum++;
           //till now we have consideredsub-strings with the given alphabet at the end, now we consider with given alphabet in middle
           //consider string "ACAXC" and character 'C'
           //left = characterPositionList[1][0]-0=1. So, there is 1 character to the left of 'C'
           left = characterPositionList[i][0]-0;
           if(characterCount[i]>1)
           {
               //right=characterPositionList[1][1]-characterPositionList[1][0]=4-1=3
               //so,there are 3 characters in right
               right = characterPositionList[i][1]-characterPositionList[i][0]-1;
               //total permutations ofcombiningthese leftand rightcharacters to form sub-strings=(left*right)
               sum+= (left*right);
               for(j=2;j<characterCount[i];j++)
               {
                   left = characterPositionList[i][j-1]-characterPositionList[i][j-2]-1;
                   right = characterPositionList[i][j]-characterPositionList[i][j-1]-1;
                   sum+= (left*right);
               }
               left = characterPositionList[i][j-1]-characterPositionList[i][j-2]-1;
           }
           right = len-characterPositionList[i][j-1]-1;
           sum+= (left*right);
           sum+= characterCount[i];
        }
    }

   return sum;
}




int main()
{
    char str[]="ACAX";
    cout<<solution(str)<<endl;
}