We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Practice
  2. Algorithms
  3. Strings
  4. Weighted Uniform Strings
  5. Discussions

Weighted Uniform Strings

Sort 566 Discussions, By:

  • kasatky
     + 28 comments

    C++

    int main(){
    string s;
    cin >> s;
    int n;
    cin >> n;    
    vector<bool> vb(10*1000*1000);    
    int mul=1;
    char prev='1';
    for(int j=0; j<s.size(); j++){
        int w = s[j]-'a'+1;
        if(s[j]==prev) {mul++; w*=mul;}
        else mul=1;
        prev = s[j];
        vb[w] = true;
    }    
    for(int a0 = 0; a0 < n; a0++){
        int x;
        cin >> x;
        if(vb[x]) cout << "Yes" << endl;
        else cout << "No" << endl;
    }    
    return 0;
}

  • parth_bhoiwala
     + 11 comments

    My approach in Python using sets and dictionary for O(1) access.

    alpha = {'a':1, 'b':2, 'c':3, 'd':4, 'e':5, 'f':6, 'g':7, 'h':8, 'i':9, 'j':10, 'k':11, 'l':12, 'm':13, 'n':14, 'o':15, 'p':16, 'q':17, 'r':18, 's':19, 't':20, 'u':21, 'v':22, 'w':23, 'x':24, 'y':25, 'z':26}

s = input().strip()
n = int(input().strip())
scores = set()
ctr=1
for i in range(len(s)):
    score = alpha[s[i]]
    ctr = ctr+1 if (i+1 != len(s) and s[i+1] == s[i]) else 1
    scores.add(score*ctr)

for a0 in range(n):
    x = int(input().strip())
    print("Yes" if x in scores else "No")

  • mrinalinishukla
     + 13 comments

    My Java Solution: Track continuous characters and reset the count on character change, use HashSet to improve performance for large strings.

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        int n = in.nextInt();
        char [] charArray = s.toCharArray();
        int contigentString = 1;
        int lastAlphaNum = 0;
        Set<Integer> numList = new HashSet<Integer>();
        for(int i=0 ;i< charArray.length; i ++){
            int alphaNum = charArray[i] -'a'+1;
            if(alphaNum == lastAlphaNum){
                contigentString++;
            }
            else{
                contigentString = 1;
                lastAlphaNum = alphaNum;
            }
            int num = (alphaNum) * contigentString;
            numList.add(num); 
        }
        for(int a0 = 0; a0 < n; a0++){
            int x = in.nextInt();
            if(numList.contains(x) ){
                System.out.println("Yes");
            }
            else{
                System.out.println("No");
            }
        }
    }

  • kegenrodrigues
     + 4 comments

    Language: Python

    Possible reason for Timeout Error

    Appending to list was creating multiple repeated values.

    Adding to set instead of appending to list solved my problem.

    This is the only difference in both the codes i have provided.

    Code With Timeout Error

    #!/bin/python3
import sys
s = input().strip()
n = int(input().strip())
seq=[]
for num in range(1,27):
    seq.append(0)
for x in sorted(set(s)):
    i = 1;
    while x * i in s:
        i += 1
    seq[ord(x)-97]=i-1 
finale=[] 			     	         #using list
for index,every in enumerate(seq):
    for sval in range(every):
        finale.append((index+1)*(sval+1))  	 #using list 
for a0 in range(n):
    x = int(input().strip())
    print("Yes" if x in finale else "No")

    Code Without Timeout Error

    #!/bin/python3
import sys
s = input().strip()
n = int(input().strip())
seq=[]
for num in range(1,27):
    seq.append(0)
for x in sorted(set(s)):
    i = 1;
    while x * i in s:
        i += 1
    seq[ord(x)-97]=i-1 
finale=set() 				#using set
for index,every in enumerate(seq):
    for sval in range(every):
        finale.add((index+1)*(sval+1)) 	#using set
for a0 in range(n):
    x = int(input().strip())
    print("Yes" if x in finale else "No")

    Hope it helps!

  • AdityaShenoy
     + 3 comments
    s = input()
n = int(input())
x = [0] * len(s)
for i in range(len(s)):
  if i != 0 and s[i - 1] == s[i]:
    x[i] = x[i-1] + ord(s[i]) - 96
  else:
    x[i] = ord(s[i]) - 96
for _ in range(n):
  print('Yes' if int(input()) in x else 'No')

    First calculate the weight at all positions of the string as a pre-processing step.
    For the weight calculation,
    1. If it is not the first element and if its previous character is same as the current character, then add the weight of current character to the previous character's stored weight and store it in array x.
    2. Else store the weight of the current character in the array x

    For eg. in string "acc"
    1st position will have weight equal to the weight of the character i.e. 1 (a=1)

    2nd position character (c) and its previous character (a) do not match hence weight of current character (c) will be stored to the array i.e. 3 (c=1)

    3rd position character (c) and its previous character (c) match hence weight of current character (c) i.e. 3 will be added to previous weight (3) totalling to 6

    Now the x array will have contents as [1, 3, 6]

    We make a hash set out of this array for faster checking of presence of a number

    Now, for every input, we just need to check whether it is present in the hash set or not and print Yes or No accordingly.

Load more conversations