Discussion on Permutations of Strings Challenge

Sort 125 Discussions, By:

3 weeks ago+ 0 comments

The following program gives correct output in code:block editor installed on my computer. but here in the Hackerrank compiler gives me Segmentation fault on one input and my other inputs are wrong. why?

int compareStringArr(char** strArr,int size){ for(int i=0;iSstored = NULL; int next_permutation(int n, char **s) { / * Complete this method * Return 0 when there is no next permutation and 1 otherwise * Modify array s to its next permutation */ static int idx = 1; static int tempidx = 1;

char *temp = NULL;

int i=0,nfac = 1,nmrfact=1,npr=1;
    int comp = 0;
    for(i=1;i<=n;i++){
     nfac = nfac * i;
    }
    for(i=1;i<=(n-2);i++){
     nmrfact = nmrfact *i;
    }
    npr = nfac /nmrfact;

if(idx==1){
    Sstored = (char**)calloc(npr,sizeof(char*));
    for(i=0;i<npr;i++){
      Sstored[i]=(char*)calloc(1000,sizeof(char));
    }
    for(i=0;i<n;i++){
     strcat(Sstored[idx-1], *(s+i));
    }
}

temp = (char*)calloc(1000,sizeof(char));

if(npr>idx){

    do{
     temp = *s;
     *s = *(s+tempidx);
     *(s+tempidx)=temp;
     idx++;

     for(i=0;i<n;i++){
      strcat(Sstored[idx-1], *(s+i));
     }

     tempidx++;
     if(tempidx==n){
        tempidx=1;
     }
     comp = compareStringArr(Sstored,idx);
    }while(comp==1);
  return 1;
}
else{
    for(i=0;i<npr;i++){
     free(Sstored[i]);
    }
    free(Sstored);
    return 0;
}

}

1 month ago+ 0 comments

void swap(char **s1, char **s2){
    char *temp = *s1 ;
    *s1 = *s2 ;
    *s2 = temp ;
}

int next_permutation(int n, char **s)
{
    int k=n-2;      //second last index
    while(k>=0){
        if( strcmp(s[k], s[k+1]) < 0 ){break;} //if from the ending the string is lexicographic then break, if not go inside (from the last) to reach the lexicographic index
        k--;
    }
    
 // end case last permutation will return 0 and stop the printing loop in the main function
    if(k==-1){return 0;}

	int l = n-1;    //last index
	while(l>k){
			if( strcmp(s[k], s[l]) < 0 ){break;}    //i.e if lexicographic then lock the l value and break the loop
			l--;
	}

	swap(&s[k], &s[l]);     //addresses of array elements ko bhej rhe hai

	int i = k+1;
	int j = n-1;

	while(j>i){
			swap(&s[i], &s[j]);
			i++;
			j--;
	}

2 months ago+ 0 comments

void swap(char **s1, char **s2)
{
    char *temp = *s1;
    *s1 = *s2;
    *s2 = temp;
}

int next_permutation(int n, char **s)
{
    for (int i = n - 2; i >= 0; i--)
    {
        if (strcmp(*(s + i), *(s + i + 1)) < 0)
        {             
            for (int j = n - 1; j > i; j--)
            {
                if (strcmp(*(s + i), *(s + j)) < 0)
                {
                    swap(s + i, s + j);

                    int mid = (n - 1 - i) / 2;
                    for (int k = 1; k <= mid; k++)
                    {
                        swap(s + i + k, s + n - 1 - k + 1);
                    }
                    return 1;
                }
            }
        }
    }
    return 0;
}

2 months ago+ 0 comments

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

void swap(char** array, int firstIndex, int secondIndex) {
    char* temp;
    temp = calloc(11, sizeof(char));
    strcpy(temp, array[firstIndex]);
    strcpy(array[firstIndex], array[secondIndex]);
    strcpy(array[secondIndex], temp);
    free(temp);
}

void reverse(char** array, int substringIndex, int n)
{
    while (substringIndex < n)
    {
        swap(array, substringIndex, n);
        substringIndex++;
        n--;
    }
}

int next_permutation(int n, char **s)
{
    int i = n - 2, q = 0, smallest = 0;
    while(i >= 0) {
        if (strcmp(s[i], s[i + 1]) < 0) {
            smallest = i + 1;
            for (q = smallest; q < n; q++) {
                if (strcmp(s[q], s[i]) > 0 && strcmp(s[q], s[smallest]) <= 0) {
                    smallest = q;
                }
            }
            swap(s, i, smallest);
            reverse(s, i + 1, n - 1);
            return 1;
        }
        i--;
    }
    return 0;
}

int main()
{
	char **s;
	int n;
	scanf("%d", &n);
	s = calloc(n, sizeof(char*));
	for (int i = 0; i < n; i++)
	{
		s[i] = calloc(11, sizeof(char));
		scanf("%s", s[i]);
	}
	do
	{
		for (int i = 0; i < n; i++)
			printf("%s%c", s[i], i == n - 1 ? '\n' : ' ');
	} while (next_permutation(n, s));
	for (int i = 0; i < n; i++)
		free(s[i]);
	free(s);
	return 0;
}

2 months ago+ 0 comments

I admit, I couldn't figure it out without explanation. Just didn't get the pattern. I found a picture of steps needed to get the next permutation on another site and just had to program the steps.

Here's my code. I hope the comments will let you understand the steps I took.

void swap (char** a, char** b){
    char* t;
    t = *a;
    *a = *b;
    *b = t;
}

int next_permutation(int n, char **s)
{

    //find longest non-incresing suffix
    for (int i = n-1; i >=1; i--){
        //printf("%d %s\n", i, s[i]);
        if (strcmp(s[i], s[i-1]) > 0) {
            //printf("%s is less than %s, i-1 (pivot point) is %d\n", s[i-1], s[i], i-1);

            int pivot = i-1;
            //find the rightmost successor of pivot in the suffix (from n-1 to i)
            for (int j = n-1; j > pivot; j--) {
                if (strcmp(s[j], s[pivot]) > 0) {
                    //swap the pivot and rightmost successor
                    swap(&s[j], &s[pivot]);
                    break;
                }
            }

            // reverse the suffix
            int iterations = (n-1-pivot)/2;
            //printf("iterations = %d\n", iterations);
            for (int k = 0; k<iterations;k++){
                swap(&s[i+k], &s[n-1-k]);
            }
            
            return 1;
        }
    }

    return 0;
}

Load more conversations