diff --git a/android/soongconfig/modules.go b/android/soongconfig/modules.go
index 9239ca9..23c8afa 100644
--- a/android/soongconfig/modules.go
+++ b/android/soongconfig/modules.go
@@ -240,12 +240,7 @@
 // string vars, bool vars and value vars created by every
 // soong_config_module_type in this build.
 type Bp2BuildSoongConfigDefinitions struct {
-	// varCache contains a cache of string variables namespace + property
-	// The same variable may be used in multiple module types (for example, if need support
-	// for cc_default and java_default), only need to process once
-	varCache map[string]bool
-
-	StringVars map[string][]string
+	StringVars map[string]map[string]bool
 	BoolVars   map[string]bool
 	ValueVars  map[string]bool
 }
@@ -255,7 +250,7 @@
 // SoongConfigVariablesForBp2build extracts information from a
 // SoongConfigDefinition that bp2build needs to generate constraint settings and
 // values for, in order to migrate soong_config_module_type usages to Bazel.
-func (defs *Bp2BuildSoongConfigDefinitions) AddVars(mtDef SoongConfigDefinition) {
+func (defs *Bp2BuildSoongConfigDefinitions) AddVars(mtDef *SoongConfigDefinition) {
 	// In bp2build mode, this method is called concurrently in goroutines from
 	// loadhooks while parsing soong_config_module_type, so add a mutex to
 	// prevent concurrent map writes. See b/207572723
@@ -263,7 +258,7 @@
 	defer bp2buildSoongConfigVarsLock.Unlock()
 
 	if defs.StringVars == nil {
-		defs.StringVars = make(map[string][]string)
+		defs.StringVars = make(map[string]map[string]bool)
 	}
 	if defs.BoolVars == nil {
 		defs.BoolVars = make(map[string]bool)
@@ -271,24 +266,29 @@
 	if defs.ValueVars == nil {
 		defs.ValueVars = make(map[string]bool)
 	}
-	if defs.varCache == nil {
-		defs.varCache = make(map[string]bool)
-	}
+	// varCache contains a cache of string variables namespace + property
+	// The same variable may be used in multiple module types (for example, if need support
+	// for cc_default and java_default), only need to process once
+	varCache := map[string]bool{}
+
 	for _, moduleType := range mtDef.ModuleTypes {
 		for _, v := range moduleType.Variables {
 			key := strings.Join([]string{moduleType.ConfigNamespace, v.variableProperty()}, "__")
 
 			// The same variable may be used in multiple module types (for example, if need support
 			// for cc_default and java_default), only need to process once
-			if _, keyInCache := defs.varCache[key]; keyInCache {
+			if _, keyInCache := varCache[key]; keyInCache {
 				continue
 			} else {
-				defs.varCache[key] = true
+				varCache[key] = true
 			}
 
 			if strVar, ok := v.(*stringVariable); ok {
+				if _, ok := defs.StringVars[key]; !ok {
+					defs.StringVars[key] = make(map[string]bool, len(strVar.values))
+				}
 				for _, value := range strVar.values {
-					defs.StringVars[key] = append(defs.StringVars[key], value)
+					defs.StringVars[key][value] = true
 				}
 			} else if _, ok := v.(*boolVariable); ok {
 				defs.BoolVars[key] = true
@@ -301,6 +301,23 @@
 	}
 }
 
+// This is a copy of the one available in soong/android/util.go, but depending
+// on the android package causes a cyclic dependency. A refactoring here is to
+// extract common utils out from android/utils.go for other packages like this.
+func sortedStringKeys(m interface{}) []string {
+	v := reflect.ValueOf(m)
+	if v.Kind() != reflect.Map {
+		panic(fmt.Sprintf("%#v is not a map", m))
+	}
+	keys := v.MapKeys()
+	s := make([]string, 0, len(keys))
+	for _, key := range keys {
+		s = append(s, key.String())
+	}
+	sort.Strings(s)
+	return s
+}
+
 // String emits the Soong config variable definitions as Starlark dictionaries.
 func (defs Bp2BuildSoongConfigDefinitions) String() string {
 	ret := ""
@@ -312,8 +329,13 @@
 	ret += starlark_fmt.PrintBoolDict(defs.ValueVars, 0)
 	ret += "\n\n"
 
+	stringVars := make(map[string][]string, len(defs.StringVars))
+	for k, v := range defs.StringVars {
+		stringVars[k] = sortedStringKeys(v)
+	}
+
 	ret += "soong_config_string_variables = "
-	ret += starlark_fmt.PrintStringListDict(defs.StringVars, 0)
+	ret += starlark_fmt.PrintStringListDict(stringVars, 0)
 
 	return ret
 }